Minimum Length of String After Deleting Similar Ends

Problem Statement

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 = "".

Try here before watching the video.

Video Solution

Java Code

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

C++ Code

class Solution {
public:
    int minimumLength(string s) {
        int start = 0, end = s.length() - 1;
        while (start < end && s[start] == s[end]) {
            char ch = s[start];
            while (start <= end && s[start] == ch) {
                start += 1;
            }
            while (end > start && s[end] == ch) {
                end -= 1;
            }
        }
        return end - start + 1;
    }
};

Python Code

class Solution:
    def minimumLength(self, s: str) -> int:
        start, end = 0, len(s) - 1
        while start < end and s[start] == s[end]:
            ch = s[start]
            while start <= end and s[start] == ch:
                start += 1
            while end > start and s[end] == ch:
                end -= 1
        return end - start + 1

Javascript Code

var minimumLength = function(s) {
    let start = 0,
        end = s.length - 1;
    while (start < end && s[start] === s[end]) {
        let ch = s[start];
        while (start <= end && s[start] === ch) {
            start += 1;
        }
        while (end > start && s[end] === ch) {
            end -= 1;
        }
    }
    return end - start + 1;
};

Go Code

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

Complexity Analysis

Time Complexity: O(N), we are iterating all the elements exactly at once.
Space Complexity: O(1), we are not utilizing any extra space.