Skip to main content

5 posts tagged with "String"

View All Tags

class Solution1:
def backspaceCompare(self, s: str, t: str) -> bool:
ss, st = [], []
for c in s:
if c != '#':
ss.append(c)
elif ss:
ss.pop()
for c in t:
if c != '#':
st.append(c)
elif st:
st.pop()
return ss == st


class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
ps, pt = len(s) - 1, len(t) - 1 # pointer
bs, bt = 0, 0 # backspace

def go_left(string, pointer, backspace):
while pointer >= 0 and (backspace or string[pointer] == '#'):
backspace += (-1) ** (string[pointer] != '#')
pointer -= 1
return pointer, backspace

while True:
(ps, bs), (pt, bt) = go_left(s, ps, bs), go_left(t, pt, bt)
if not (ps >= 0 and pt >= 0 and s[ps] == t[pt]):
return ps == pt == -1
ps -= 1
pt -= 1

from collections import Counter


class Solution:
def getHint(self, s: str, g: str) -> str:
a, b = 0, 0
cs, cg = Counter(), Counter()
for i in range(len(s)):
if s[i] == g[i]:
a += 1
continue
if cg[s[i]]:
cg[s[i]] -= 1
b += 1
else:
cs[s[i]] += 1
if cs[g[i]]:
cs[g[i]] -= 1
b += 1
else:
cg[g[i]] += 1
return f'{a}A{b}B'

class Solution:
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271
def characterReplacement(self, s: str, k: int) -> int:
c, mf = {}, 0 # counter, max_freq
l, N = 0, len(s)
for r in range(N):
c[s[r]] = c.get(s[r], 0) + 1
mf = max(mf, c[s[r]])
if not ((r + 1) - l - mf <= k): # shift right
c[s[l]] -= 1
l += 1
# find next if same
return N - l # length


class Solution2:
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271
def characterReplacement(self, s: str, k: int) -> int:
result = 0
c, mf = {}, 0 # counter, max_freq
for r in range(len(s)):
c[s[r]] = c.get(s[r], 0) + 1
mf = max(mf, c[s[r]])
if result - mf >= k:
c[s[r - result]] -= 1
else:
result += 1 # update when more
return result


class SolutionBS: # TODO: review
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/2805777
def characterReplacement(self, s: str, k: int) -> int:
def too_long(length: int):
c, mf = {}, 0
l = 0
for r in range(len(s)):
c[s[r]] = c.get(s[r], 0) + 1
if r + 1 - l > length:
c[s[l]] -= 1
l += 1
mf = max(mf, c[s[r]])
if length - mf <= k:
return False
return True

l, r = 0, len(s)
while l < r:
m = (l + r) // 2
length = m + 1
l, r = (l, m) if too_long(length) else (m + 1, r)
return (l - 1) + 1