Minimum Length of String After Deleting Similar Ends — Medium Problem & Solution

Problem statement

You may repeat this operation any number of times on a string s:

1. pick a non-empty prefix of identical characters;
2. pick a non-empty suffix of identical characters made of the same character;
3. the prefix and suffix must not overlap;
4. delete both.

Return the minimum length s can be reduced to.

Example 1

Input: s = "ca"
Output: 2
Explanation: The two ends differ, so nothing can be removed.

Example 2

Input: s = "cabaabac"
Output: 0
Explanation: Strip c's, then a's, then b's, then the middle aa.

Example 3

Input: s = "aabccabba"
Output: 3
Explanation: After stripping the a's and then the b's, "cca" remains... the two pointers stop at "bca".

Constraints

• 1 <= s.length <= 100000
• s consists of the characters a, b and c.

How to solve Minimum Length of String After Deleting Similar Ends

The operation only ever removes matching runs from the two ends, so a two-pointer walk that consumes whole runs simulates the best possible sequence of operations directly.

Approach

1. Set lo = 0 and hi = n - 1.
2. While lo < hi and the two characters match, note the character and advance lo past its whole run, then retreat hi past its whole run — both guarded so the pointers cannot cross wildly.
3. Return hi - lo + 1, which is 0 when the pointers crossed.

Why it works

Deleting less than a full run is never better: the leftover characters of that run are still at the end and still match, so the next operation could remove them anyway. Greedily removing whole runs therefore reaches the minimum, and the loop stops exactly when the ends stop matching — at which point no operation applies.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Removing one character per side instead of the whole run makes the loop do extra rounds but, worse, can stop early when the counts differ.
• The lo <= hi and hi >= lo guards inside the inner loops are what stop the pointers from running past each other on a uniform string.
• The answer can be 0; returning hi - lo instead of hi - lo + 1 is off by one.

Reference solution

Python

def minimumLength(s: str) -> int:
    lo, hi = 0, len(s) - 1
    while lo < hi and s[lo] == s[hi]:
        c = s[lo]
        while lo <= hi and s[lo] == c:
            lo += 1
        while hi >= lo and s[hi] == c:
            hi -= 1
    return hi - lo + 1

JavaScript

var minimumLength = function(s) {
    var lo = 0, hi = s.length - 1;
    while (lo < hi && s.charAt(lo) === s.charAt(hi)) {
        var c = s.charAt(lo);
        while (lo <= hi && s.charAt(lo) === c) lo++;
        while (hi >= lo && s.charAt(hi) === c) hi--;
    }
    return hi - lo + 1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium