Scale Engineer

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:

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

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.

public int minimumLength(String s) {    while (s.length() > 1 && s.charAt(0) == s.charAt(s.length() - 1)) {        char c = s.charAt(0);        int left = 0;        int right = s.length() - 1;                while (left <= right && s.charAt(left) == c) {            left++;        }                // This check is crucial for strings like "aaaa"        if (left > right) {            return 0;        }                while (right >= left && s.charAt(right) == c) {            right--;        }                s = s.substring(left, right + 1);    }    return s.length();}

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.

Solutions

class Solution {public  int minimumLength(String s) {    int i = 0, j = s.length() - 1;    while (i < j && s.charAt(i) == s.charAt(j)) {      while (i + 1 < j && s.charAt(i) == s.charAt(i + 1)) {        ++i;      }      while (i < j - 1 && s.charAt(j) == s.charAt(j - 1)) {        --j;      }      ++i;      --j;    }    return Math.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 →

Next problem