1750. Minimum Length of String after Deleting Similar Ends - Explanation

Description

You may remove a nonempty prefix and a nonempty suffix from s in one operation if both consist entirely of the same character. The two pieces must not overlap. Repeat this operation as often as you wish and return the smallest remaining length. A single character cannot be used as both pieces.

Example 1:

Input: s = "a"

Output: 1

Explanation: There is only one character, so a nonempty prefix and suffix cannot be chosen without overlapping.

Example 2:

Input: s = "aa"

Output: 0

Explanation: Choose the first "a" as the prefix and the second "a" as the suffix. Removing both leaves an empty string.

Example 3:

Input: s = "ab"

Output: 2

Explanation: The first and last characters differ, so no operation can be performed. Both characters remain.

Constraints:

1 <= s.length <= 100000
Each character is a, b, or c.

Topics

Two Pointers String

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Two Pointers Technique - Using pointers at both ends of an array/string to process elements
Greedy Algorithms - Making locally optimal choices that lead to a globally optimal solution
String Manipulation - Working with character comparisons and substrings

1. Greedy + Two Pointers

Intuition

We can repeatedly trim matching characters from both ends of the string. The operation requires the prefix and suffix to consist of the same character, and we must remove at least one character from each end.

Using two pointers starting at opposite ends, we check if both point to the same character. If they do, we greedily remove all consecutive occurrences of that character from both ends. This greedy choice is optimal because removing more characters now can only help (or not hurt) future operations.

Algorithm

Initialize two pointers: l at the start and r at the end of the string.
While l < r and s[l] == s[r]:
- Store the matching character.
- Move l right past all consecutive occurrences of this character.
- Move r left past all consecutive occurrences of this character.
The remaining length is r - l + 1.
If the pointers cross (l > r), the entire string was deleted, returning 0.

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

        while l < r and s[l] == s[r]:
            tmp = s[l]
            while l <= r and s[l] == tmp:
                l += 1
            while l <= r and s[r] == tmp:
                r -= 1
        return r - l + 1

public class Solution {
    public int minimumLength(String s) {
        int l = 0, r = s.length() - 1;

        while (l < r && s.charAt(l) == s.charAt(r)) {
            char tmp = s.charAt(l);
            while (l <= r && s.charAt(l) == tmp) {
                l++;
            }
            while (l <= r && s.charAt(r) == tmp) {
                r--;
            }
        }
        return r - l + 1;
    }
}

class Solution {
public:
    int minimumLength(string s) {
        int l = 0, r = s.length() - 1;

        while (l < r && s[l] == s[r]) {
            char tmp = s[l];
            while (l <= r && s[l] == tmp) {
                l++;
            }
            while (l <= r && s[r] == tmp) {
                r--;
            }
        }
        return r - l + 1;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    minimumLength(s) {
        let l = 0,
            r = s.length - 1;

        while (l < r && s[l] === s[r]) {
            const tmp = s[l];
            while (l <= r && s[l] === tmp) {
                l++;
            }
            while (l <= r && s[r] === tmp) {
                r--;
            }
        }
        return r - l + 1;
    }
}

public class Solution {
    public int MinimumLength(string s) {
        int l = 0, r = s.Length - 1;

        while (l < r && s[l] == s[r]) {
            char tmp = s[l];
            while (l <= r && s[l] == tmp) {
                l++;
            }
            while (l <= r && s[r] == tmp) {
                r--;
            }
        }
        return r - l + 1;
    }
}

func minimumLength(s string) int {
    l, r := 0, len(s)-1

    for l < r && s[l] == s[r] {
        tmp := s[l]
        for l <= r && s[l] == tmp {
            l++
        }
        for l <= r && s[r] == tmp {
            r--
        }
    }
    return r - l + 1
}

class Solution {
    fun minimumLength(s: String): Int {
        var l = 0
        var r = s.length - 1

        while (l < r && s[l] == s[r]) {
            val tmp = s[l]
            while (l <= r && s[l] == tmp) {
                l++
            }
            while (l <= r && s[r] == tmp) {
                r--
            }
        }
        return r - l + 1
    }
}

class Solution {
    func minimumLength(_ s: String) -> Int {
        let chars = Array(s)
        var l = 0
        var r = chars.count - 1

        while l < r && chars[l] == chars[r] {
            let tmp = chars[l]
            while l <= r && chars[l] == tmp {
                l += 1
            }
            while l <= r && chars[r] == tmp {
                r -= 1
            }
        }
        return r - l + 1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Allowing Pointers to Cross Without Proper Bounds

When moving pointers past consecutive matching characters, they can cross each other if the entire remaining string consists of the same character. The inner while loops must check l <= r to prevent accessing invalid indices or producing negative lengths.

Requiring Non-Empty Prefix and Suffix Separately

The operation removes a non-empty prefix and a non-empty suffix of the same character. A common mistake is allowing one side to be empty, which violates the problem constraints. Both pointers must move at least once per valid operation.