LeetCode 1750 - Minimum Length of String After Deleting Similar Ends

LeetCode Problem 1750

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

The problem gives us a string s containing only the characters 'a', 'b', and 'c'. We may repeatedly perform a deletion operation on the string. In each operation, we must remove:

• A non-empty prefix where every character is the same
• A non-empty suffix where every character is the same
• Both groups must contain the same character
• The prefix and suffix cannot overlap

Our goal is to minimize the remaining length of the string after performing the operation as many times as we want.

The important detail is that we are not limited to removing just one character from each side. If the left side begins with several identical characters, we may remove all of them together. Similarly, if the right side ends with several identical characters, we may remove all of them together. As long as both sides use the same character and do not overlap, the operation is valid.

For example, in "aabccabba":

• We can remove "aa" from the left and "a" from the right
• The remaining string becomes "bccabb"

The input size can be as large as 10^5, so any algorithm that repeatedly creates new strings or scans large portions many times may become too slow. This strongly suggests we need a linear-time solution.

Several edge cases are important:

• Strings where the first and last characters are different, because no operation is possible
• Strings made entirely of one character, because the whole string may disappear
• Very short strings such as length 1 or 2
• Cases where removing one layer exposes another removable layer
• Cases where repeated characters on both sides must be skipped completely, not one character at a time

A naive implementation may incorrectly remove only one character per step instead of removing all contiguous matching characters.

Approaches

Brute Force Approach

A brute force strategy would simulate the process directly using repeated string operations.

At every step:

1. Check whether the first and last characters are equal.
2. If they are different, stop.
3. Otherwise, identify the maximal prefix consisting of that character.
4. Identify the maximal suffix consisting of that character.
5. Remove both parts by creating a new substring.
6. Repeat until no more deletions are possible.

This approach is correct because it directly follows the rules of the problem. Every valid operation removes matching character blocks from both ends.

However, this implementation is inefficient if done using repeated substring creation. Each removal may require constructing a new string of size O(n), and this could happen many times. In the worst case, the total complexity becomes O(n^2).

Optimal Approach

The key observation is that we never need to physically modify the string.

The only part of the string that matters is the current active window between two pointers:

• left, pointing to the beginning
• right, pointing to the end

If s[left] != s[right], no operation is possible and we are done.

If they are equal, then every contiguous occurrence of that character on both sides will eventually be removed. Therefore, instead of deleting one operation at a time, we can skip all matching characters immediately.

This leads naturally to a two-pointer solution:

• Move left forward past all copies of the matching character
• Move right backward past all copies of the matching character
• Continue until the pointers cross or the boundary characters differ

Because every character is visited at most once, the algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated substring creation and rescanning
Optimal	O(n)	O(1)	Two pointers shrink the active window efficiently

Algorithm Walkthrough

1. Initialize two pointers:

• left = 0
• right = len(s) - 1

These pointers represent the current active substring. 2. Continue processing while:

• left < right
• s[left] == s[right]

If the characters at the ends are different, no valid operation exists anymore. 3. Store the current character:

current_char = s[left]

This is the character we will remove from both ends. 4. Move the left pointer forward while:

• left <= right
• s[left] == current_char

This skips the entire matching prefix. 5. Move the right pointer backward while:

• left <= right
• s[right] == current_char

This skips the entire matching suffix. 6. Repeat the process until:

• The pointers cross, meaning the entire string was removed
• Or the boundary characters differ

7. The remaining length is:

right - left + 1

If the pointers crossed, this value naturally becomes 0.

Why it works

The algorithm relies on the fact that whenever the first and last characters match, removing fewer than all contiguous copies of that character is never beneficial. Any remaining copies at either end would still block future operations. Therefore, the optimal strategy is always to remove the entire matching block from both sides immediately.

The two pointers always define the exact remaining substring after all processed removals. Since every removable layer is handled completely, the final remaining window is minimal.

Python Solution

class Solution:
    def minimumLength(self, s: str) -> int:
        left = 0
        right = len(s) - 1

        while left < right and s[left] == s[right]:
            current_char = s[left]

            while left <= right and s[left] == current_char:
                left += 1

            while left <= right and s[right] == current_char:
                right -= 1

        return right - left + 1

The implementation directly follows the two-pointer algorithm.

The left and right pointers track the current valid substring. The outer loop continues only while the boundary characters match. Once they differ, no more deletions are possible.

Inside the loop, the current removable character is stored in current_char. The inner loops then skip every contiguous occurrence of that character from both sides.

The conditions left <= right prevent out-of-bounds access and correctly handle cases where the entire string disappears.

Finally, the remaining substring length is computed as right - left + 1.

Go Solution

func minimumLength(s string) int {
    left := 0
    right := len(s) - 1

    for left < right && s[left] == s[right] {
        currentChar := s[left]

        for left <= right && s[left] == currentChar {
            left++
        }

        for left <= right && s[right] == currentChar {
            right--
        }
    }

    return right - left + 1
}

The Go implementation is nearly identical to the Python version.

Strings in Go are byte slices internally, and since the input contains only ASCII characters 'a', 'b', and 'c', indexing with s[i] is completely safe.

No special handling for integer overflow is required because the maximum string length is only 10^5.

Worked Examples

Example 1

Input:

s = "ca"

Initial state:

left	right	s[left]	s[right]
0	1	c	a

The boundary characters differ immediately, so no operation is possible.

Remaining length:

1 - 0 + 1 = 2

Output:

2

Example 2

Input:

s = "cabaabac"

Initial state:

Step	left	right	Current Window
Start	0	7	cabaabac

Boundary characters are both 'c'.

Remove all 'c' from both sides:

Step	left	right	Current Window
After removing c	1	6	abaaba

Boundary characters are both 'a'.

Remove all 'a' from both sides:

Step	left	right	Current Window
After removing a	2	5	baab

Boundary characters are both 'b'.

Remove all 'b' from both sides:

Step	left	right	Current Window
After removing b	3	4	aa

Boundary characters are both 'a'.

Remove all 'a' from both sides:

Step	left	right	Current Window
After removing a	5	4	empty

Pointers crossed, so the remaining length is 0.

Output:

0

Example 3

Input:

s = "aabccabba"

Initial state:

Step	left	right	Current Window
Start	0	8	aabccabba

Boundary characters are both 'a'.

Skip all 'a' from left and right:

Step	left	right	Current Window
After removing a	2	7	bccabb

Boundary characters are both 'b'.

Skip all 'b' from left and right:

Step	left	right	Current Window
After removing b	3	5	cca

Now boundary characters are 'c' and 'a', which differ.

Remaining length:

5 - 3 + 1 = 3

Output:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited at most once by either pointer
Space	O(1)	Only a few variables are used

The algorithm is linear because both pointers move only inward and never move backward. Every character is processed at most one time. No additional data structures proportional to input size are required.

Test Cases

solution = Solution()

assert solution.minimumLength("ca") == 2  # no removable ends
assert solution.minimumLength("cabaabac") == 0  # entire string removed
assert solution.minimumLength("aabccabba") == 3  # partial removal

assert solution.minimumLength("a") == 1  # single character
assert solution.minimumLength("aa") == 0  # both characters removed
assert solution.minimumLength("ab") == 2  # different characters

assert solution.minimumLength("aba") == 1  # remove outer a characters
assert solution.minimumLength("abba") == 0  # repeated nested removals
assert solution.minimumLength("abcba") == 1  # center character remains

assert solution.minimumLength("aaaaa") == 0  # entire string same character
assert solution.minimumLength("bbbbbbbb") == 0  # long uniform string

assert solution.minimumLength("aabbaa") == 0  # multiple layers removed
assert solution.minimumLength("cabac") == 1  # symmetric removals

assert solution.minimumLength("aacccbaa") == 3  # removal stops midway
assert solution.minimumLength("bbcacbb") == 0  # complete collapse after layers

assert solution.minimumLength("abc") == 3  # no valid operation
assert solution.minimumLength("aaccaa") == 2  # middle section remains

Test	Why
"ca"	Verifies no removal case
"cabaabac"	Verifies complete deletion
"aabccabba"	Verifies layered removals
"a"	Smallest possible input
"aa"	Two identical characters
"ab"	Two different characters
"aba"	Single center character remains
"abba"	Entire string collapses
"abcba"	Nested symmetric removals
"aaaaa"	All characters identical
"bbbbbbbb"	Large uniform block
"aabbaa"	Multiple full reductions
"cabac"	Symmetric pattern
"aacccbaa"	Removal stops before full collapse
"bbcacbb"	Repeated reductions lead to empty
"abc"	No removable boundaries
"aaccaa"	Inner unmatched substring survives

Edge Cases

One important edge case is when the string length is 1. Since the operation requires both a prefix and a suffix that do not overlap, no deletion is possible. The implementation handles this naturally because the condition left < right is false immediately.

Another critical edge case is when the entire string consists of the same character, such as "aaaaaa". A buggy implementation might stop too early or incorrectly leave one character behind. In this solution, both pointers continue skipping matching characters until they cross, producing a final length of 0.

A third tricky case occurs when repeated removals expose new removable boundaries. For example, "cabaabac" initially removes only 'c', but after that, the remaining substring exposes matching 'a' characters, then matching 'b' characters. The outer loop continues processing until no further removals are possible, ensuring all layers are handled correctly.

Another subtle edge case is when large contiguous blocks appear on both ends with different sizes, such as "aabccabba". The rules allow removing prefixes and suffixes of different lengths as long as they contain the same character. The implementation correctly skips the entire contiguous region on both sides independently, regardless of block size differences.