Leetcode 1750. Minimum Length of String After Deleting Similar Ends
Problem statement :
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:
- Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
- Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
- The prefix and the suffix should not intersect at any index.
- The characters from the prefix and suffix must be the same.
- Delete both the prefix and the suffix.
- Return the minimum length of s after performing the above operation any number of times (possibly zero times).
Examples :
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 = "".
Constraints:
1 <= s.length <= 105 s only consists of characters ‘a’, ‘b’, and ‘c’.
Solution :
class Solution:
def minimumLength(self, s: str) -> int:
left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
char = s[left]
while left <= right and s[left] == char:
left += 1
while right >= left and s[right] == char:
right -= 1
return right - left + 1