Minimum Length of String After Deleting Similar Ends

Med

#1602Time: O(N^2) in the worst case. For a string like "abacada...", each step removes only a few characters, and creating a substring can take O(N) time. With up to O(N) such steps, the total time is quadratic.Space: O(N), where N is the length of the string. In each iteration, `substring` can create a new string object, potentially of length O(N).

Patterns

Two Pointers

Data structures

String

Prompt

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:

Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
The prefix and the suffix should not intersect at any index.
The characters from the prefix and suffix must be the same.
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 <= 10⁵
s only consists of characters 'a', 'b', and 'c'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It repeatedly finds the prefix and suffix with identical characters, removes them by creating a new substring, and continues this process in a loop until no more characters can be removed. While intuitive, this method is inefficient because string manipulation, especially creating substrings in a loop, is computationally expensive.

Algorithm

Start a loop that continues as long as the string s has more than one character.
In the loop, check if the first and last characters of s are the same. If not, break the loop.
If they are the same, identify the character c.
Find the extent of the prefix of c's by finding the first index left not equal to c.
Find the extent of the suffix of c's by finding the last index right not equal to c.
If the entire string consists of c (i.e., left pointer moves past the right pointer), the result is 0.
Otherwise, update s by creating a new substring that excludes the identified prefix and suffix using s.substring(left, right + 1).
After the loop terminates, return the length of the final string s.

Walkthrough

The algorithm works on the string s iteratively. In each iteration, it checks if the string has more than one character and if its first and last characters match. If they do, it identifies the common character c. It then finds the first index left that does not contain c from the beginning and the last index right that does not contain c from the end. If the left pointer crosses the right pointer, it implies the entire string consisted of the character c, and the resulting length is 0. Otherwise, the string s is updated to the substring between left and right. The loop continues until the ends don't match or the string becomes too short. Finally, the length of the resulting string s is returned.

1public int minimumLength(String s) {2    while (s.length() > 1 && s.charAt(0) == s.charAt(s.length() - 1)) {3        char c = s.charAt(0);4        int left = 0;5        int right = s.length() - 1;6        7        while (left <= right && s.charAt(left) == c) {8            left++;9        }10        11        // This check is crucial for strings like "aaaa"12        if (left > right) {13            return 0;14        }15        16        while (right >= left && s.charAt(right) == c) {17            right--;18        }19        20        s = s.substring(left, right + 1);21    }22    return s.length();23}

Complexity

Time

O(N^2) in the worst case. For a string like "abacada...", each step removes only a few characters, and creating a substring can take O(N) time. With up to O(N) such steps, the total time is quadratic.

Space

O(N), where N is the length of the string. In each iteration, `substring` can create a new string object, potentially of length O(N).

Trade-offs

Pros

Simple to understand and implement as it directly models the problem statement.

Cons

Highly inefficient due to the overhead of creating new string objects in each iteration.
Worst-case time complexity is quadratic, which is too slow for large inputs.
Can lead to high memory consumption due to the creation of many temporary string objects.

A much more efficient approach uses two pointers, left and right, initialized to the start and end of the string, respectively. These pointers are moved inwards, skipping over the prefixes and suffixes that are to be deleted. This avoids the costly operation of creating new strings in each step, leading to an optimal linear time solution with constant space.

Algorithm

Initialize two pointers: left at the start of the string (index 0) and right at the end (s.length() - 1).
Use a while loop that continues as long as left < right (to ensure prefix and suffix don't overlap) and s.charAt(left) == s.charAt(right).
Inside the loop, save the character c = s.charAt(left).
Increment left in a nested loop while left <= right and s.charAt(left) == c to skip the entire prefix.
Decrement right in another nested loop while right >= left and s.charAt(right) == c to skip the entire suffix.
Once the main loop terminates, the remaining part of the string is conceptually between indices left and right.
Return the length of this remaining part, which is calculated as right - left + 1.

Walkthrough

This greedy algorithm uses two pointers, left starting at index 0 and right at s.length() - 1. The core of the algorithm is a while loop that runs as long as left is less than right and the characters at s[left] and s[right] are identical. This condition ensures we can perform an operation and that the prefix and suffix do not overlap.

Inside the loop:

The common character c at the ends is noted.
The left pointer is advanced forward past all consecutive occurrences of c.
The right pointer is moved backward past all consecutive occurrences of c.

This process effectively "deletes" the prefix and suffix without actually modifying the string or creating new ones. The loop terminates when the characters at left and right are different, or when left meets or surpasses right. The final length of the remaining string is the number of characters between the final left and right positions, inclusive. This is calculated as right - left + 1. If left has moved past right, this formula correctly yields 0 or a negative number, which corresponds to an empty remaining string.

1public int minimumLength(String s) {2    int left = 0;3    int right = s.length() - 1;4 5    while (left < right && s.charAt(left) == s.charAt(right)) {6        char c = s.charAt(left);7        // Move left pointer to the right past all occurrences of c8        while (left <= right && s.charAt(left) == c) {9            left++;10        }11        // Move right pointer to the left past all occurrences of c12        while (right >= left && s.charAt(right) == c) {13            right--;14        }15    }16    17    // The remaining length is the distance between the two pointers18    return right - left + 1;19}

Complexity

Time

O(N), where N is the length of the string. Each pointer, `left` and `right`, traverses the string at most once in a single pass.

Space

O(1). Only a constant amount of extra space is used for the two pointers and a character variable, regardless of the input string size.

Trade-offs

Pros

Extremely efficient with linear time complexity.
Optimal space complexity, using only a constant amount of extra space.
Avoids expensive string creation and manipulation operations.

Cons

The logic with multiple nested loops and pointer updates might be slightly less intuitive to grasp initially compared to direct simulation.

Solutions

Solution

1class Solution {2public3  int minimumLength(String s) {4    int i = 0, j = s.length() - 1;5    while (i < j && s.charAt(i) == s.charAt(j)) {6      while (i + 1 < j && s.charAt(i) == s.charAt(i + 1)) {7        ++i;8      }9      while (i < j - 1 && s.charAt(j) == s.charAt(j - 1)) {10        --j;11      }12      ++i;13      --j;14    }15    return Math.max(0, j - i + 1);16  }17}

1class Solution {2public:3  int minimumLength(string s) {4    int i = 0, j = s.size() - 1;5    while (i < j && s[i] == s[j]) {6      while (i + 1 < j && s[i] == s[i + 1]) {7        ++i;8      }9      while (i < j - 1 && s[j] == s[j - 1]) {10        --j;11      }12      ++i;13      --j;14    }15    return max(0, j - i + 1);16  }17};

1class Solution : def minimumLength ( self , s : str ) -> int : i , j = 0 , len ( s ) - 1 while i < j and s [ i ] == s [ j ]: while i + 1 < j and s [ i ] == s [ i + 1 ]: i += 1 while i < j - 1 and s [ j - 1 ] == s [ j ]: j -= 1 i , j = i + 1 , j - 1 return max ( 0 , j - i + 1 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem