Minimum Length of String After Deleting Similar Ends

Share

Delete matching characters from both ends (same char prefix from left, suffix from right). Minimize length.

Example 1
Input: s="ca" → Output: 2
Example 2
Input: s="cabaabac" → Output: 0
Example 3
Input: s="aabccabba" → Output: 3

Solution Approach

Two pointers: while left < right and chars match, delete all matching chars on both sides.

  • left=0, right=n-1
  • While left < right and s[left]==s[right]
  • Advance left past all s[left] chars
  • Advance right back past all s[right] chars
  • Return max(0, right-left+1)
Java
public int minimumLength(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right && s.charAt(left) == s.charAt(right)) {
        char c = s.charAt(left);
        while (left <= right && s.charAt(left) == c) left++;
        while (left <= right && s.charAt(right) == c) right--;
    }
    return right - left + 1;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)