Quick Overview

A string problem that asks for the shortest contiguous substring to delete from a lowercase string so that the joined prefix and suffix contain no repeated character, returning 0 when all characters are already distinct. It tests reasoning about prefixes, suffixes and character counts under a linear-time bound.

Shortest Substring to Delete So Every Remaining Character Is Unique

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Given a string `s` of lowercase English letters, delete one contiguous substring and join the remaining prefix and suffix together. Return the minimum length of a deleted substring that leaves every character of the joined string appearing at most once. If all characters of `s` are already distinct, return 0. ### Function Signature ```python def min_deletion_for_distinct(s: str) -> int: ``` ### Rules - A deletion is a pair `0 <= l <= r <= len(s)`; it removes `s[l:r]` and leaves `s[:l] + s[r:]`. The pair `l == r` deletes nothing. - A deletion is valid when no character occurs more than once in `s[:l] + s[r:]`. The empty string and every one-character string are valid results. - Return the minimum `r - l` over all valid deletions as a single integer. Only the length is returned, so the answer is unique even when several substrings of that length work. ### Constraints - `1 <= len(s) <= 10^5` - `s` contains only the letters `'a'` to `'z'`. ### Examples **Example 1** ```text Input: s = "aabb" Output: 2 ``` Delete `s[1:3] = "ab"`: `"a" + "b" = "ab"`, which has no repeated character. Deleting any single character leaves either two `a`s or two `b`s. **Example 2** ```text Input: s = "abcde" Output: 0 ``` All characters are already distinct, so nothing needs to be deleted. **Example 3** ```text Input: s = "abcab" Output: 2 ``` Delete `s[0:2] = "ab"` to leave `"cab"`. Both `a` and `b` occur twice, and deleting one character removes an occurrence of only one of them, so no deletion of length 1 works.

Overview: A string problem that asks for the shortest contiguous substring to delete from a lowercase string so that the joined prefix and suffix contain no repeated character, returning 0 when all characters are already distinct. It tests reasoning about prefixes, suffixes and character counts under a linear-time bound.

Read the full Oracle Software Engineer interview experience this question came from

Given a string `s` of lowercase English letters, delete one contiguous substring (it may be empty) and join the remaining prefix and suffix together. Return the minimum length of a deleted substring that leaves every character of the joined string appearing at most once. If all characters of `s` are already distinct, return 0. **Rules** - A deletion is a pair of indices `0 <= l <= r <= len(s)`; it removes `s[l:r]` and leaves `s[:l] + s[r:]`. The pair `l == r` deletes nothing. - A deletion is valid when no character occurs more than once in `s[:l] + s[r:]`. The empty string and every one-character string are valid results, so a valid deletion always exists. - Return the minimum `r - l` over all valid deletions as a single integer. Only the length is returned, so the answer is unique even when several substrings of that length work. The answer is between 0 and `len(s) - 1`, so it always fits in a 32-bit signed integer. **Example 1** ```text Input: s = "aabb" Output: 2 ``` Delete `s[1:3] = "ab"`: `"a" + "b" = "ab"`, which has no repeated character. Deleting any single character leaves either two `a`s or two `b`s. **Example 2** ```text Input: s = "abcab" Output: 2 ``` Delete `s[0:2] = "ab"` to leave `"cab"`. Both `a` and `b` occur twice, and deleting one character removes an occurrence of only one of them, so no deletion of length 1 works. **Constraints** - `1 <= len(s) <= 10^5` - `s` contains only the letters `'a'` to `'z'`.

Constraints

  • 1 <= len(s) <= 10^5
  • s contains only the letters 'a' to 'z'.

Examples

Input: ('a',)

Expected Output: 0

Explanation: Single character: already distinct, so l == r deletes nothing.

Input: ('zz',)

Expected Output: 1

Explanation: Two copies of the highest letter 'z': only one can remain, so one character is deleted.

Hints

  1. Whatever survives the deletion is a prefix of s followed by a suffix of s. Each piece must be repeat-free on its own, and the two pieces must not share a letter.
  2. The alphabet has only 26 letters. What does that say about how long the surviving prefix or suffix can be?
  3. Example 'abcab' shows why counting repeated letters is not enough: the deleted part must be contiguous, so one deleted character can remove an extra copy of only one letter.

Shortest Substring Deletion to Make All Characters Distinct

hardOracleSoftware Engineer

Given a string s of lowercase English letters, delete one contiguous substring (it may be empty) and join the remaining prefix and suffix together. Return the minimum length of a deleted substring that leaves every character of the joined string appearing at most once. If all characters of s are already distinct, return 0.

Rules

  • A deletion is a pair of indices 0 <= l <= r <= len(s); it removes s[l:r] and leaves s[:l] + s[r:]. The pair l == r deletes nothing.
  • A deletion is valid when no character occurs more than once in s[:l] + s[r:]. The empty string and every one-character string are valid results, so a valid deletion always exists.
  • Return the minimum r - l over all valid deletions as a single integer. Only the length is returned, so the answer is unique even when several substrings of that length work. The answer is between 0 and len(s) - 1, so it always fits in a 32-bit signed integer.

Example 1

Input:  s = "aabb"
Output: 2

Delete s[1:3] = "ab": "a" + "b" = "ab", which has no repeated character. Deleting any single character leaves either two as or two bs.

Example 2

Input:  s = "abcab"
Output: 2

Delete s[0:2] = "ab" to leave "cab". Both a and b occur twice, and deleting one character removes an occurrence of only one of them, so no deletion of length 1 works.

Constraints

  • 1 <= len(s) <= 10^5
  • s contains only the letters 'a' to 'z'.

Examples

Example 1
Input
('a',)
Output
0
Notes
Single character: already distinct, so l == r deletes nothing.
Example 2
Input
('zz',)
Output
1
Notes
Two copies of the highest letter 'z': only one can remain, so one character is deleted.

Constraints

  • •1 <= len(s) <= 10^5
  • •s contains only the letters 'a' to 'z'.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def min_deletion_for_distinct(s) -> int:
Sample call
min_deletion_for_distinct('a')
Language
Case 1
Input
('a',)
Expected
0
Case 2
Input
('zz',)
Expected
1

Browse More Questions

Show the approach

Approach

Whatever survives a deletion is the prefix s[:l] followed by the suffix s[r:]. That string is repeat-free exactly when the prefix is repeat-free, the suffix is repeat-free, and the two share no letter.

Algorithm: let P be the length of the longest repeat-free prefix of s (P <= 26 because there are only 26 letters). For each l = 0, 1, ..., P, start with r = len(s) and a table holding the letters of s[:l]; then move r left while r > l and s[r - 1] is not already in the table, adding each newly kept letter. The scan stops at the first letter that would repeat, or when r reaches l. Record r - l and return the smallest value recorded.

Invariant: throughout a scan, s[:l] + s[r:] is repeat-free.

Correctness: for a fixed l, validity is monotone in r, because raising r only removes characters from the suffix. Once s[r - 1] conflicts with a kept letter, every smaller r still keeps that conflicting character and is invalid, so the stopping r is the smallest valid r for that l. Every valid deletion keeps a repeat-free prefix, so its l is one of 0..P and its r is at least the smallest valid r for that l; hence the minimum over the tried l is the optimum.

Edge cases: a single character or an already distinct string gives 0 (the l = 0 scan runs all the way to r = 0); a string of one repeated letter gives len(s) - 1; deletions of a pure prefix (l = 0) and of a pure suffix (r = len(s)) are both covered because l = 0 is tried and every scan starts at r = len(s). Each scan adds one new letter per step, so it takes at most 26 steps, and at most 27 prefixes are tried.

Time complexity:
O(min(n, 26)^2)
Space complexity:
O(1)