{x}
blog image

Minimum Length of String After Deleting Similar Ends

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

 

Constraints:

  • 1 <= s.length <= 105
  • s only consists of characters 'a', 'b', and 'c'.

Solution Explanation: Minimum Length of String After Deleting Similar Ends

This problem asks to find the minimum length of a string after repeatedly removing prefixes and suffixes that meet specific conditions. The conditions are:

  1. Prefix and Suffix are Non-Empty: Both the prefix and suffix must contain at least one character.
  2. Prefix and Suffix are Homogenous: All characters within the prefix must be the same, and all characters within the suffix must be the same.
  3. Prefix and Suffix are Identical: The characters in the prefix and suffix must be the same.
  4. No Overlap: The prefix and suffix cannot share any indices.

The most efficient approach uses a two-pointer technique.

Algorithm:

  1. Initialization: Initialize two pointers, left (pointing to the beginning of the string) and right (pointing to the end of the string).

  2. Iteration: While left is less than right and the characters at left and right are the same:

    • Inner Loops: First, extend the left pointer as long as the character at left is the same as the character at left + 1. This finds the longest homogenous prefix. Then, similarly, extend the right pointer inwards as long as the character at right is the same as the character at right - 1. This finds the longest homogenous suffix.
    • Advance Pointers: After finding the longest homogenous prefix and suffix, move left one step to the right and right one step to the left. This simulates the removal of the prefix and suffix.

  3. Result: After the while loop, if left is greater than or equal to right, it means the entire string was removed; return 0. Otherwise, the remaining string's length is right - left + 1; return this value.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string. This is because the pointers traverse the string at most once.
  • Space Complexity: O(1), as the algorithm uses only a constant amount of extra space for pointers.

Code Implementation (Python):

class Solution:
    def minimumLength(self, s: str) -> int:
        left, right = 0, len(s) - 1
        while left < right and s[left] == s[right]:
            # Extend left pointer to find longest homogenous prefix
            while left + 1 < right and s[left] == s[left + 1]:
                left += 1
            #Extend right pointer to find longest homogenous suffix
            while left < right -1 and s[right] == s[right - 1]:
                right -= 1
            left += 1  #Move pointers after removing prefix and suffix
            right -= 1
        return max(0, right - left + 1) #Return the remaining length or 0 if entire string is removed

The code in other languages (Java, C++, Go, TypeScript, Rust, C) follows the same algorithm and has the same time and space complexity. The only differences are syntax and specific library functions used.