A. Keep Multiplying Found Values by Two (opens new window)

DETAILS

def findFinalValue(self, A: List[int], num: int) -> int:
        sa = set(A)
        while num in sa:
            num *= 2
        return num

B. All Divisions With the Highest Score of a Binary Array (opens new window)

Prefix sum and suffix sum.

DETAILS

def maxScoreIndices(self, A: List[int]) -> List[int]:
        cur, ans = sum(A), [sum(A)]
        for a in A:
            if a == 0:
                cur += 1
            else:
                cur -= 1
            ans.append(cur)
        m = max(ans)
        return [i for i, a in enumerate(ans) if a == m]

C. Find Substring With Given Hash Value (opens new window)

Rolling Hash

DETAILS

def subStrHash(self, s: str, p: int, mod: int, k: int, hv: int) -> str:
        n = len(s)
        def helper(ch):
            return ord(ch) - ord('a') + 1
        
        pk = pow(p, k, mod)
        res, cur = 0, 0
        
        for i in range(n - 1, n - 1 - k, -1):
            cur = (cur * p + helper(s[i])) % mod
        if cur == hv:
            res = i
        
        for i in range(n - 1 - k, -1, -1):
            cur = (cur * p + helper(s[i])) % mod
            cur = (cur - helper(s[i + k]) * pk) % mod
            if cur == hv:
                res = i
        return s[res: res + k]

D. Groups of Strings (opens new window)

DSU.

DETAILS

class DSU:
    def __init__(self, n):
        self.root = list(range(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):
        self.root[self.find(x)] = self.find(y)

class Solution:
    def groupStrings(self, A: List[str]) -> List[int]:        
        c = collections.defaultdict(int)
        for a in A:
            c["".join(sorted(a))] += 1
    
        A = list(set(["".join(sorted(a)) for a in A]))
        n = len(A)
                
        idx = collections.defaultdict(int)
        dsu = DSU(n)

        def add(base):
            for i in range(26):
                if not base & 1 << i:
                    yield base ^ 1 << i
        def dele(base):
            for i in range(26):
                if base & 1 << i:
                    if base - (1 << i) != 0:
                        yield base - (1 << i)        
        def rep(base):
            pre = []
            new = []
            for i in range(26):
                if base & 1 << i:
                    pre.append(i)
                else:
                    new.append(i)
            for p in pre:
                for n in new:
                    yield base - (1 << p) + (1 << n)                
        
        for i, a in enumerate(A):
            base = 0
            for ch in a:
                base += 1 << ord(ch) - ord('a')
            idx[base] = i

        for base in idx.keys():
            for new in add(base):
                if new in idx:
                    dsu.union(idx[base], idx[new])
            for new in dele(base):
                if new in idx:
                    dsu.union(idx[base], idx[new])
            for new in rep(base):
                if new in idx:
                    dsu.union(idx[base], idx[new])
        
        group = collections.defaultdict(int)
        for a in A:
            base = 0
            for ch in a:
                base += 1 << ord(ch) - ord('a')
            cnum = c[a]
            group[dsu.find(idx[base])] += cnum
        
        return [len(group), max(group.values())]