Shortest Substring to Delete So Every Remaining Character Is Unique
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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
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
- 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.
- The alphabet has only 26 letters. What does that say about how long the surviving prefix or suffix can be?
- 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.