1750. Minimum Length of String After Deleting Similar Ends Medium

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:

1. Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
2. Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
3. The prefix and the suffix should not intersect at any index.
4. The characters from the prefix and suffix must be the same.
5. 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).

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".

Approach

Input: A string s containing only 'a', 'b', 'c'

Output: Return the minimum length of the string after repeatedly removing identical non-empty prefixes and suffixes.

This is a classic opposite-direction two pointers problem.

We can define two pointers: left = 0, right = len(s) - 1, iterating from the ends of the string towards the middle.

Whenever we find s[left] == s[right], it means the current character can be deleted as a prefix and suffix:

• Move the left pointer to the right, skipping all consecutive prefixes equal to that character;
• Move the right pointer to the left, skipping all consecutive suffixes equal to that character.

Repeat the above process until left >= right or we can no longer delete.

The length of the final remaining string is right - left + 1, which is returned as the answer.

Implementation

python

class Solution:
    def minimumLength(self, s: str) -> int:
        # Define two pointers moving towards the center from both ends of the string
        left, right = 0, len(s) - 1

        # Try to remove identical prefixes and suffixes from both sides if the characters match
        while left < right and s[left] == s[right]:
            char = s[left]  # Record the character to be deleted

            # Move left pointer to the right, skipping all consecutive char
            while left <= right and s[left] == char:
                left += 1

            # Move right pointer to the left, skipping all consecutive char
            while left <= right and s[right] == char:
                right -= 1

        # The length of the remaining string is right - left + 1 (returns 0 when left > right)
        return right - left + 1

javascript

/**
 * @param {string} s
 * @return {number}
 */
const minimumLength = function(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right && s[left] == s[right]) {
        const char = s[left];

        while (left <= right && s[left] == char) {
            left ++;
        }

        while (left <= right && s[right] == char) {
            right --;
        }
    }

    return right - left + 1;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

1750. Minimum Length of String After Deleting Similar Ends (English)1750. 删除字符串两端相同字符后的最短长度 (Chinese)