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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Length of String After Deleting Similar Ends

Number: 1850

Difficulty: Medium

Paid? No

Companies: Amazon, Goldman Sachs

Problem Description

Given a string s that contains only the characters 'a', 'b', and 'c', you can repeatedly delete a non-empty prefix and a non-empty suffix if all characters in the prefix (and similarly in the suffix) are the same and both the prefix and suffix contain the same character, with the two parts not overlapping. The objective is to determine the minimum length of the string after performing these operations any number of times.

Key Insights

  • Two pointers can be used: one starting from the beginning and the other from the end of the string.
  • Only perform deletions when the first and last characters are the same.
  • Once the characters at both ends match, extend the deletion to include all contiguous occurrences of that character from both ends.
  • Stop when the two pointers meet or cross, or when the characters at the two pointers differ.
  • The answer is the length of the remaining “middle” section of the string (or 0 if all characters are deleted).

Space and Time Complexity

Time Complexity: O(n) – Each character is processed at most once. Space Complexity: O(1) – Only constant extra space is used.

Solution

The solution uses a two-pointer strategy. We initialize one pointer at the start and one at the end of the string. As long as the two pointers have not crossed and the characters at both pointers are the same, we remove all consecutive occurrences of that character from both ends. This is achieved by moving the left pointer forward and the right pointer backward until a different character is encountered. The final answer is computed as the length of the substring left between the two pointers. If all characters are removed, the answer is 0.

Code Solutions

# Python solution for "Minimum Length of String After Deleting Similar Ends"
def minimumLength(s: str) -> int:
    # Initialize two pointers: left at the start and right at the end of the string.
    left, right = 0, len(s) - 1
    
    # While the left pointer is to the left of the right pointer and the characters they point to are the same
    while left < right and s[left] == s[right]:
        # Store the current character to be removed from both ends.
        current_char = s[left]
        
        # Move the left pointer to the right as long as the current character is the same.
        while left <= right and s[left] == current_char:
            left += 1
        # Move the right pointer to the left as long as the current character is the same.
        while left <= right and s[right] == current_char:
            right -= 1
    
    # Return the length of the remaining substring. If left > right, the string is empty.
    return max(0, right - left + 1)

# Example Usage:
print(minimumLength("cabaabac"))  # Expected output: 0
← Back to All Questions