You are given a string s.
You can perform the following process on s any number of times:
i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].i that is equal to s[i].i that is equal to s[i].Return the minimum length of the final string s that you can achieve.
Example 1:
Input: s = "abaacbcbb"
Output: 5
Explanation:
We do the following operations:
s = "bacbcbb".s = "acbcb".Example 2:
Input: s = "aa"
Output: 2
Explanation:
We cannot perform any operations, so we return the length of the original string.
Constraints:
1 <= s.length <= 2 * 105s consists only of lowercase English letters.The idea is to use two pointers, start from both ends and move towards the center to find possible deletions. By tracking pairs of identical characters, we can optimally remove pairs until no more operations are possible.
This solution uses a two-pointer approach to check both ends of the string s. It increments the left pointer and decrements the right pointer if the characters at these positions are equal, effectively tracking and removing the mirrored characters towards the center.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, as each element is checked at most once. Space Complexity: O(1), as no additional data structures are used.
Instead of using the two-pointer method, this approach uses a stack to help determine operations. As we iterate through the string, we identify characters that can be removed based on previous ones and reduce the string progressively.
In this C solution, a stack is used to evaluate and track removable characters while iterating through the string. The stack helps manage operations like collapsing character pairs efficiently.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Two-pointer Technique | Time Complexity: O(n), where n is the length of the string, as each element is checked at most once. Space Complexity: O(1), as no additional data structures are used. |
| Stack-based Reduction | Time Complexity: O(n), Space Complexity: O(n). |
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 Operations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor