Shortest Deletion for Distinct Characters
Problem statement
You are given a string s of lowercase English letters. You may remove one contiguous block of characters from s. The part before the block and the part after it are then joined back together. The block may also be empty, which removes nothing.
Return the smallest block length for which no letter appears more than once in the joined result. If no letter repeats in s, the answer is 0.
Function
minDeletionLength(s: String) → intExamples
Example 1
s = "aabb"return = 2Delete the middle substring "ab" (indices 1 and 2). The remaining prefix "a" and suffix "b" join into "ab", where no letter repeats. Deleting only one character always leaves a repeated a or b, so 2 is the minimum.
Example 2
s = "cabcbd"return = 2c and b each appear twice, so at least one of each must be deleted, which takes at least 2 characters. Deleting "bc" at indices 2 and 3 leaves "ca" and "bd", which join into "cabd" with no repeats.
Example 3
s = "xyz"return = 0No letter repeats, so nothing needs to be deleted.
Constraints
1 <= s.length <= 105scontains only lowercase English letters.