A. Minimum Recolors to Get K Consecutive Black Blocks (opens new window)

Slidwng window of fixed length.

DETAILS

def minimumRecolors(self, A: str, k: int) -> int:
        c = collections.Counter(A[:k])
        ans = c.get('W', 0)
        for i in range(k, len(A)):
            c[A[i]] += 1
            c[A[i - k]] -= 1
            ans = min(ans, c.get('W', 0))
        return ans

B. Time Needed to Rearrange a Binary String (opens new window)

Brute Force.

DETAILS

def secondsToRemoveOccurrences(self, s: str) -> int:
        A, d = list(map(int, list(s))), 0     
        for _ in range(1000):
            cnt, prev = 0, 0
            for i in range(len(s) - 1, 0, -1):
                if A[i] == 1 and A[i - 1] == 0 and prev == 0:
                    cnt += 1
                    A[i], A[i - 1] = A[i - 1], A[i]
                    prev = 1
                else:
                    prev = 0
            if cnt == 0:
                return d
            d += 1
        return -1

C. Shifting Letters II (opens new window)

Prefix sum.

DETAILS

def shiftingLetters(self, S: str, A: List[List[int]]) -> str:
        n = len(S)
        P = [0] * (n + 1)
        for l, r, a in A:
            if a == 1:
                P[l] += 1
                P[r + 1] -= 1
            else:
                P[l] -= 1
                P[r + 1] += 1
        
        cur = 0
        ans = ""
        
        for i, s in enumerate(S):
            cur += P[i]
            ans += chr(ord('a') + (ord(s) - ord('a') + cur) % 26)
        
        return ans

2382. Maximum Segment Sum After Removals (opens new window)

DSU on the reversed removal array. (or Max-stack on removal array)

DETAILS

class UF:
    def __init__(self, n):
        self.root = list(range(n))
        self.rk = [0] * n
    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            if self.rk[rx] > self.rk[ry]:
                rx, ry = ry, rx
            self.root[rx] = ry
            self.rk[ry] += self.rk[rx]
    def getSize(self, x):
        rx = self.find(x)
        return self.rk[rx]


class Solution:
    def maximumSegmentSum(self, A: List[int], Q: List[int]) -> List[int]:
        n = len(A)
        uf = UF(n)
        ans = [0]
        maxs = 0
        for q in Q[::-1]:
            uf.rk[q] = A[q]
            if q > 0 and uf.rk[q - 1]:
                uf.union(q, q - 1)
            if q < n - 1 and uf.rk[q + 1]:
                uf.union(q, q + 1)
            maxs = max(maxs, uf.getSize(q))
            ans.append(maxs)
        return ans[::-1][1:]