Problem statement

https://binarysearch.com/problems/Half-Monotonous-String/

Solution

For each symbol x we can check if it is pivot, that is left part need to have elements < x and right part should have element >= x. To make it quicker we can precalculate counters for the left and right parts. Then when we iterate over all possible x we just need to choose corresponding elements. Also we will use check function for direct and reversed strings and also we need to deal with the case of all equal elements.

Complexity

It is O(n + m^2), where n = len(s) and m is the size of alphabet. Space is O(m). Notice, that it can be made O(n + m) if we use cumulative sums for left and right parts.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        
        def check(s):
            lft = Counter(s[:n//2])
            rgh = Counter(s[n//2:])
            ans = 0
            for x in "bcdefghijklmnopqrstuvwxyz":
                p1 = sum(f for s, f in lft.items() if s < x)
                p2 = sum(f for s, f in rgh.items() if s >= x)
                ans = max(ans, p1 + p2)
            return ans

        if not s: return 0
        return n - max(check(s), check(s[::-1]), Counter(s).most_common(1)[0][1])