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'.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), since it navigates through the string at minimal overhead.
Space Complexity: O(n) due to recursion depth management.
| 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. |
Minimum Length of String after Deleting Similar Ends - Leetcode 1750 - Python • NeetCodeIO • 9,454 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