Minimum Length of String After Deleting Similar Ends

Intuition

The tag of this problem is Two Pointers. But I do think it's also a kind of greedy problem.

The basic idea of this problem is that, when you picking the prefix and suffix, you should always pick the longest one. For example, for bbab, the prefix can either be bb or b. But if you choose a non-longest prefix, you will not know whether there will be still another b in the end of the new string.

Then it simply becomes a general two pointers problem.

Solution


class Solution:
    def minimumLength(self, s: str) -> int:
        if len(s) <= 1:
            return len(s)

        start = 0
        end = len(s) - 1
        while end > start:
            if s[end] != s[start]:
                break
            c = s[start]
            while start <= end and s[start] == c:
                start += 1
            while start <= end < len(s) and s[end] == c:
                end -= 1

        return end - start + 1