We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Length of String After Deleting Similar Ends

Difficulty: Medium

Problem Description

Given a string s consisting only of characters a, b, and c, you are asked to apply an algorithm that involves deleting non-empty prefixes and suffixes of equal characters, provided they are the same and do not intersect. Your goal is to determine the minimum length of the string after performing this operation any number of times.

Key Insights

  • The prefix and suffix must consist of the same character and cannot overlap.
  • The problem can be reduced by removing matching characters from both ends until they differ.
  • If the entire string can be removed through this operation, the result will be an empty string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we may need to traverse the string up to two times (once from each end). Space Complexity: O(1), as we are using a constant amount of extra space regardless of the input size.

Solution

The approach involves using two pointers: one starting from the beginning of the string and the other from the end. We will move both pointers inward while the characters at both pointers are the same. This way, we can efficiently find the remaining characters that cannot be removed. Once the pointers meet or cross, the length of the remaining string will be the answer.

Code Solutions

def minimumLength(s: str) -> int:
    left, right = 0, len(s) - 1
    
    while left < right and s[left] == s[right]:
        char = s[left]
        # Move left pointer to the right while the character is the same
        while left <= right and s[left] == char:
            left += 1
        # Move right pointer to the left while the character is the same
        while left <= right and s[right] == char:
            right -= 1
            
    return right - left + 1
← Back to All Questions