# 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())]