Minimum Length of String After Deleting Similar Ends

Problem

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 _theminimum length of _s after performing the above operation any number of times (possibly zero times).

Examples

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^5
• s only consists of characters 'a', 'b', and 'c'.

Solution

Method 1 – Two Pointers

Intuition

We use two pointers to shrink the string from both ends as long as the characters at both ends are the same. We keep removing matching prefixes and suffixes until the pointers meet or the characters differ.

Approach

1. Initialize two pointers, l at the start and r at the end of the string.
2. While l < r and s[l] == s[r], move both pointers inward, skipping all consecutive matching characters from both ends.
3. Repeat until the characters at both ends differ or the pointers cross.
4. The answer is r - l + 1.

Code

C++

class Solution {
public:
    int minimumLength(string s) {
        int l = 0, r = s.size() - 1;
        while (l < r && s[l] == s[r]) {
            char c = s[l];
            while (l <= r && s[l] == c) ++l;
            while (r >= l && s[r] == c) --r;
        }
        return r - l + 1;
    }
};

Go

func minimumLength(s string) int {
    l, r := 0, len(s)-1
    for l < r && s[l] == s[r] {
        c := s[l]
        for l <= r && s[l] == c { l++ }
        for r >= l && s[r] == c { r-- }
    }
    return r - l + 1
}

Java

class Solution {
    public int minimumLength(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r && s.charAt(l) == s.charAt(r)) {
            char c = s.charAt(l);
            while (l <= r && s.charAt(l) == c) l++;
            while (r >= l && s.charAt(r) == c) r--;
        }
        return r - l + 1;
    }
}

Kotlin

class Solution {
    fun minimumLength(s: String): Int {
        var l = 0
        var r = s.length - 1
        while (l < r && s[l] == s[r]) {
            val c = s[l]
            while (l <= r && s[l] == c) l++
            while (r >= l && s[r] == c) r--
        }
        return r - l + 1
    }
}

Python

def minimum_length(s: str) -> int:
    l, r = 0, len(s) - 1
    while l < r and s[l] == s[r]:
        c = s[l]
        while l <= r and s[l] == c:
            l += 1
        while r >= l and s[r] == c:
            r -= 1
    return r - l + 1

Rust

impl Solution {
    pub fn minimum_length(s: String) -> i32 {
        let s = s.as_bytes();
        let (mut l, mut r) = (0, s.len() - 1);
        while l < r && s[l] == s[r] {
            let c = s[l];
            while l <= r && s[l] == c { l += 1; }
            while r >= l && s[r] == c { r -= 1; }
        }
        (r as i32) - (l as i32) + 1
    }
}

TypeScript

class Solution {
    minimumLength(s: string): number {
        let l = 0, r = s.length - 1;
        while (l < r && s[l] === s[r]) {
            const c = s[l];
            while (l <= r && s[l] === c) l++;
            while (r >= l && s[r] === c) r--;
        }
        return r - l + 1;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of s. Each character is checked at most twice.
• 🧺 Space complexity: O(1), only pointers and a few variables are used.