class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
ht: dict[str, list[str]] = {}
for s in strs:
key = ''.join(sorted((s)))
ht[key] = ht.get(key, [])
ht[key].append(s)
return list(ht.values())
class SolutionR1: # O(n*n) / O(n) ? str slice
def numDecodings(self, s: str) -> int:
m = {'': 1}
def recur(s=s):
if s in m:
return m[s]
m[s] = 0
if s[0] != '0':
m[s] += recur(s[1:])
if 10 <= int(s[:2]) <= 26:
m[s] += recur(s[2:])
return m[s]
return recur()
class SolutionR2: # O(n) / O(n)
def numDecodings(self, s: str) -> int:
m = {len(s): 1}
def recur(i=0):
if i in m:
return m[i]
m[i] = 0
if s[i] != '0':
m[i] += recur(i + 1)
if 10 <= int(s[i : i + 2]) <= 26:
m[i] += recur(i + 2)
return m[i]
return recur()
class Solution1: # O(n) / O(n)
def numDecodings(self, s: str) -> int:
dp = [0] * (len(s) + 1)
dp[0], dp[1] = 1, int(s[0] != '0')
for i in range(len(s) - 1):
if s[i + 1] != '0':
dp[i + 2] += dp[i + 1]
if 10 <= int(s[i : i + 2]) <= 26:
dp[i + 2] += dp[i]
return dp[-1]
class Solution2: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b = 1, int(s[0] != '0')
for i in range(len(s) - 1):
c = 0
if s[i + 1] != '0':
c += b
if 10 <= int(s[i : i + 2]) <= 26:
c += a
a, b = b, c
return b
class Solution3: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b = 1, int(s[0] != '0')
for i in range(len(s) - 1):
one, two = s[i + 1] != '0', 10 <= int(s[i : i + 2]) <= 26
a, b = b, b * one + a * two
return b
class Solution4: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b, p = 0, int(bool(s)), ''
for c in s:
tmp = b
if c == '0':
b = 0
if 10 <= int(p + c) <= 26:
b += a
a, p = tmp, c
return b
class Solution: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b, p = 0, int(bool(s)), ''
for c in s:
one, two = c != '0', 10 <= int(p + c) <= 26
a, b, p = b, b * one + a * two, c
return b
class Solution1:
def lengthOfLongestSubstring(self, s: str) -> int:
result, chars = 0, set()
for j, c in enumerate(s):
while c in chars:
i = j - len(chars)
chars.remove(s[i])
chars.add(c)
result = max(result, len(chars))
return result
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
result, i, chars = 0, 0, {}
for j, char in enumerate(s):
i = max(i, chars.get(char, -1) + 1)
chars[char] = j
result = max(result, j - i + 1)
return result
from collections import Counter
class Solution:
def minDeletions(self, s: str) -> int:
result = 0
used: set[int] = set()
for c in Counter(s).values():
while c and c in used:
result += 1
c -= 1
used.add(c)
return result
class Solution:
def finalString(self, s: str) -> str:
buf = []
for c in s:
if c == 'i':
buf = buf[::-1]
else:
buf.append(c)
return ''.join(buf)
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
for i in range(len(text1)):
for j in range(len(text2)):
if text1[i] == text2[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
return dp[-1][-1]
class Solution:
def letterCombinations(self, digits: str):
LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
letters = [LETTERS[i] for i in map(int, digits)]
def backtracking(comb: str, i: int):
if i == len(digits):
yield comb
return
for char in letters[i]:
yield from backtracking(comb + char, i + 1)
yield from backtracking('', 0) if digits else []
class Solution1:
def letterCombinations(self, digits: str) -> list[str]:
result = []
def backtracking(comb: str, letters: list[str]):
if not letters:
return result.append(comb)
for char in letters[0]:
backtracking(comb + char, letters[1:])
LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
backtracking('', [LETTERS[i] for i in map(int, digits)])
return result if digits else []
class Solution2:
def letterCombinations(self, digits: str) -> list[str]:
LETTERS = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
letters = [LETTERS[i] for i in map(int, digits)]
result = []
def backtracking(comb: str, i: int):
if i == len(digits):
return result.append(comb)
for char in letters[i]:
backtracking(comb + char, i + 1)
backtracking('', 0)
return result if digits else []
from collections import defaultdict
class UndergroundSystem:
def __init__(self):
checkInStationNameT = checkOutStationNameT = str
checkInTimeT = travelTimeT = int
idT = countT = int
self.check_in: dict[idT, tuple[checkInTimeT, checkInStationNameT]] = {}
self.time: defaultdict[
tuple[checkInStationNameT, checkOutStationNameT], tuple[travelTimeT, countT]
] = defaultdict(lambda: (0, 0))
def checkIn(self, id: int, stationName: str, t: int) -> None:
self.check_in[id] = (t, stationName)
def checkOut(self, id: int, stationName: str, t: int) -> None:
check_in_time, check_in_station_name = self.check_in.pop(id)
_key = check_in_station_name, stationName
_travel_time, _count = self.time[_key]
self.time[_key] = _travel_time + (t - check_in_time), _count + 1
def getAverageTime(self, startStation: str, endStation: str) -> float:
_key = startStation, endStation
travel_time, count = self.time[_key]
return travel_time / count
class Solution1:
def simplifyPath(self, path: str) -> str:
stack = []
for p in path.split('/'):
if p == '..':
stack.pop() if stack else None
elif p and p != '.':
stack.append(p)
return '/' + '/'.join(stack)
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for p in path.split('/'):
d = {'': stack, '.': stack, '..': stack[:-1]}
stack = d.get(p, stack + [p])
return '/' + '/'.join(stack)
from typing import Optional
class Node:
def __init__(self, is_end: bool = False):
self.is_end = is_end
self.children: dict[str, Node] = {}
def __repr__(self):
return f'''{'! ' if self.is_end else ''}{self.children}'''
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
node = self.root
for c in word:
node.children[c] = node.children.get(c, Node())
node = node.children[c]
node.is_end = True
def _last_node_same_with(self, word: str) -> Optional[Node]:
node = self.root
for c in word:
if c not in node.children:
return
node = node.children[c]
return node
def search(self, word: str) -> bool:
node = self._last_node_same_with(word)
return bool(node) and node.is_end
def startsWith(self, word: str) -> bool:
node = self._last_node_same_with(word)
return bool(node)
class Solution:
def isValid(self, s: str) -> bool:
P = {
'(': ')',
'{': '}',
'[': ']',
}
stack = []
for c in s:
if stack and P.get(stack[-1]) == c:
stack.pop()
else:
stack.append(c)
return not stack
class Solution:
def mergeAlternately(self, w1: str, w2: str) -> str:
L1, L2 = len(w1), len(w2)
result = []
for i in range(max(L1, L2)):
if i < L1:
result.append(w1[i])
if i < L2:
result.append(w2[i])
return ''.join(result)
class Solution:
def multiply(self, num1: str, num2: str) -> str:
ZERO = '0'
if ZERO in (num1, num2):
return ZERO
def ord_(x):
return ord(x) - ord(ZERO)
def chr_(x):
return chr(x + ord(ZERO))
L1, L2 = len(num1) - 1, len(num2) - 1
result = []
carry = 0
i = 0
while (i <= L1 + L2) or carry:
j = max(0, i - L2)
while j <= min(i, L1):
n1, n2 = num1[L1 - j], num2[L2 - i + j]
carry += ord_(n1) * ord_(n2)
j += 1
result.append(chr_(carry % 10))
carry //= 10
i += 1
return ''.join(result)[::-1]
import heapq
from collections import Counter
class Solution1:
def topKFrequent(self, words: list[str], k: int) -> list[str]:
c = Counter(words)
return [x for x in sorted(c, key=lambda key: (-c[key], key))][:k]
class Solution:
def topKFrequent(self, words: list[str], k: int) -> list[str]:
c = Counter(words)
return heapq.nsmallest(k, c, key=lambda key: (-c[key], key))
class Solution1:
def backspaceCompare(self, s: str, t: str) -> bool:
S = '#'
ss, st = [], []
for c in s:
if c != S:
ss.append(c)
elif ss:
ss.pop()
for c in t:
if c != S:
st.append(c)
elif st:
st.pop()
return ss == st
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def go_left(string, pointer, backspace):
S = '#'
while pointer >= 0 and (backspace or string[pointer] == S):
backspace += (-1) ** (string[pointer] != S)
pointer -= 1
return pointer, backspace
ps, pt = len(s) - 1, len(t) - 1 # pointer
bs, bt = 0, 0 # 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: # O(n) / O(n)
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
def characterReplacement(self, s: str, k: int) -> int:
c = {} # counter
mf = 0 # max_freq
i = 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if not ((j - i + 1) - mf <= k): # shift right
c[s[i]] -= 1
i += 1
return len(s) - i # length
class Solution2: # O(n) / O(n)
# https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
def characterReplacement(self, s: str, k: int) -> int:
c = {}
mf, i = 0, 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if i - mf >= k:
c[s[j - i]] -= 1
else:
i += 1 # update when more
return i
class SolutionBS: # O(log(n)) / O(n)
# 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, i = 0, 0
for j, char in enumerate(s):
c[char] = c.get(char, 0) + 1
mf = max(mf, c[char])
if length - mf <= k:
return False
if j - i + 1 > length:
c[s[i]] -= 1
i += 1
return True
l, r = 0, len(s)
while l < r:
m = (l + r) // 2
l, r = (l, m) if too_long(length=m + 1) else (m + 1, r)
return (l - 1) + 1
from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> list[int]:
result, s, P = [], s + ' ', len(p)
cp, cs = Counter(p), Counter(s[:P])
for i in range(len(s) - P):
if cp == cs:
result.append(i)
cs.subtract(s[i])
cs.update(s[i + P])
return result
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
result = []
for i, c in enumerate(strs[0]):
if not all([i < len(s) and c == s[i] for s in strs]):
break
result.append(c)
return ''.join(result)
class Solution:
def longestPalindrome(self, s: str) -> int:
r, pool = 0, set()
for c in s:
if c in pool:
pool.remove(c)
r += 1
else:
pool.add(c)
return r * 2 + bool(pool)