Ctrl K

Thin Out Repeated Letters

Medium
You are given a string text. A move works like this: choose a position i that has a letter equal to text[i] somewhere on its left and somewhere on its right. Then erase the nearest such letter on the left of i and the nearest one on its right. The letter at i itself stays. You may make as many moves as you like. Return the smallest length the string can reach.
Example 1
text="xxxyxx" → 2

There are five xs: pick a middle one and erase its nearest x on each side, then do it once more, leaving one x. The lone y cannot be touched. That gives 2.

Example 2
text="mmnn" → 4

No letter has a copy of itself on both sides, so the string stays as it is.

Example 3
text="aaaa" → 2

Pick the second a and erase the first and the third, leaving two as and no more moves.

Constraints
  • 1 ≤ len(text) ≤ 2·10⁵
  • text consists of lowercase English letters
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsA Hint for a Digit Guess MediumCharacters Grouped by Count MediumMost Searched Words MediumNo Twin Letters Side by Side MediumDomain Visit Rollup Medium
loading Python…
Input
text="xxxyxx"
Expected
2

Run checks the first 3 tests in your browser. Submit checks all 50 tests on the server, hidden ones included.