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.
The two pointers approach uses two indices to represent the start and end of the string. The idea is to check for matching characters from both ends and shrink the string until the characters differ. Loop through the string, adjusting these pointers to remove any prefixes and suffixes with matching characters. This method is efficient as it only requires a single pass through the string.
This C implementation uses a two-pointer approach to achieve the goal. Two pointers, left and right, are initialized at the start and end of the string, respectively. As long as the characters at these pointers match, both pointers are adjusted inward until they meet or characters differ. The remaining string length is calculated and returned as the result.
Time Complexity: O(n), where n is the length of the string, because each character is visited at most twice.
Space Complexity: O(1), as no additional space is used apart from variables.
This recursive approach tries to minimize the string length by removing valid prefixes and suffixes. The base case is when no more valid removals are possible, and the remaining string length is minimal. Each recursive call attempts to strip away the symmetric ends and proceeds with the interior until the results match.
This C program uses a recursive function recursiveLength to mimic the elimination process. It checks character consistency at the string bounds and develops further recursive calls, adjusting boundaries until no more symmetrical character matches exist.
Time Complexity: O(n), since it navigates through the string at minimal overhead.
Space Complexity: O(n) due to recursion depth management.
We define two pointers i and j to point to the head and tail of the string s respectively, then move them to the middle until the characters pointed to by i and j are not equal, then max(0, j - i + 1) is the answer.
The time complexity is O(n) and the space complexity is O(1). Where n is the length of the string s.
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n), where n is the length of the string, because each character is visited at most twice. |
| Recursive Elimination Approach | Time Complexity: O(n), since it navigates through the string at minimal overhead. |
| Two pointers | — |
| 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. |
Minimum Length of String after Deleting Similar Ends - Leetcode 1750 - Python • NeetCodeIO • 9,918 views views
Watch 9 more video solutions →Practice Minimum Length of String After Deleting Similar Ends with our built-in code editor and test cases.
Practice on FleetCode