Watch 10 video solutions for Minimum Length of String After Deleting Similar Ends, a medium level problem involving Two Pointers, String. This walkthrough by NeetCodeIO has 9,918 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string s consisting only of characters 'a', 'b', and 'c'. You are asked to apply the following algorithm on the string any number of times:
s where all the characters in the prefix are equal.s where all the characters in this suffix are equal.Return the minimum length of s after performing the above operation any number of times (possibly zero times).
Example 1:
Input: s = "ca" Output: 2 Explanation: You can't remove any characters, so the string stays as is.
Example 2:
Input: s = "cabaabac" Output: 0 Explanation: An optimal sequence of operations is: - Take prefix = "c" and suffix = "c" and remove them, s = "abaaba". - Take prefix = "a" and suffix = "a" and remove them, s = "baab". - Take prefix = "b" and suffix = "b" and remove them, s = "aa". - Take prefix = "a" and suffix = "a" and remove them, s = "".
Example 3:
Input: s = "aabccabba" Output: 3 Explanation: An optimal sequence of operations is: - Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb". - Take prefix = "b" and suffix = "bb" and remove them, s = "cca".
Constraints:
1 <= s.length <= 105s only consists of characters 'a', 'b', and 'c'.Problem Overview: You are given a string s. If the first and last characters are the same, you can delete the entire group of identical characters from both ends. This process repeats until the characters at the ends differ or the string becomes empty. The task is to return the minimum possible length after performing these deletions.
Approach 1: Two Pointers (O(n) time, O(1) space)
This problem fits naturally with the two pointers pattern. Maintain two indices: left starting at the beginning of the string and right at the end. If s[left] and s[right] match, that character becomes the deletion target. Move left forward while characters equal this target, and move right backward while they also match it. This effectively removes the entire matching prefix and suffix group in one step.
The key insight: once the edge characters match, you must delete the entire contiguous block of that character from both sides. Partial removal is never beneficial. Each character is visited at most once by either pointer, giving linear time complexity O(n). The algorithm uses only a few integer variables, so the extra space is O(1). This is the optimal solution and the one typically expected in interviews involving string manipulation.
Approach 2: Recursive Elimination (O(n) time, O(n) recursion stack)
The same logic can be implemented recursively. If the first and last characters match, scan inward to skip all identical characters on both sides. Then recursively solve the remaining substring defined by the updated indices. Each recursive call reduces the string boundaries, mimicking the same elimination process as the iterative approach.
This approach highlights the repeated substructure of the problem: after removing symmetric groups, the remaining substring behaves exactly like the original problem. While the total number of processed characters is still linear, recursion introduces stack overhead. In the worst case, the recursion depth can reach O(n), leading to O(n) auxiliary space.
Recommended for interviews: The Two Pointers approach is the expected solution. It demonstrates strong understanding of boundary scanning and in-place reduction techniques common in two pointers problems. The recursive version is useful for reasoning about the elimination process, but interviewers typically prefer the iterative solution because it avoids recursion overhead and achieves O(1) space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n) | O(1) | Best general solution. Efficient for large strings and typically expected in coding interviews. |
| Recursive Elimination | O(n) | O(n) | Useful for conceptual understanding of repeated boundary reduction and recursive string processing. |