BinarySearch 0163 Sort String by Flipping

Problem statement

https://binarysearch.com/problems/Sort-String-by-Flipping/

Solution

Equal to Leetcode 0926. Flip String to Monotone Increasing.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        s = [i == "y" for i in s]
        acc, n = [0] + list(accumulate(map(int, s))), len(s)
        return min(2*acc[i] + n - i - acc[-1] for i in range(n+1))