A circuit board carries a row of n test points, each stamped with a lowercase letter naming its signal group. A technician may repeatedly perform the following action on the points still present on the board: choose any surviving test point at some position, then remove the nearest surviving test point sharing that same letter to its left and the nearest surviving test point sharing that same letter to its right — but only if both such same-letter neighbors currently exist among the surviving points; the chosen test point itself is never removed. The technician may repeat this action any number of times (including zero), in any order and on any surviving point, each time recomputing nearest same-letter neighbors among whatever test points remain. Determine the minimum number of test points that can remain on the board after performing zero or more such actions.
A single line containing the string s of test-point labels.
A single integer: the minimum number of test points that can remain.
Example 1
Input
abaacbcbb
Expected
5
Explanation
Letter a appears 3 times (odd), so it can be reduced to 1 surviving occurrence; letter b appears 4 times (even), so it reduces to 2; letter c appears 2 times (even), which is too few to ever trigger the action, so it stays at 2. The minimum total length is 1 + 2 + 2 = 5.
Example 2
Input
aabbcc
Expected
6
Explanation
Every letter (a, b, c) appears exactly 2 times. The action requires a chosen test point plus a distinct same-letter neighbor on each side — at least 3 occurrences of that letter — so with only 2 occurrences of each letter, no action can ever be performed. All 6 test points remain, so the answer is 6.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →