My website

class Solution: def minFlipsMonoIncr(self, s: str) -> int: """tc O(N) sc O(1) main idea: DP imagine for substring s[:i] the format is 0000111, current s[i] is '1' so we dont need to make changes when current s[i] is '0' , we have two options to make (1) convert current '0'... [Read More]

class Solution: def uniqueLetterString(self, s: str) -> int: """ tc O(N) sc O(N) two rounds main idea: check left and right position, cnt = (cur-leftPos) * (rightPos - cur) 1. for each char, save all the index appeared in the s 2. loop through all the charector, loop through all... [Read More]

class Solution: def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]: """tc O(V+E) sc O(V+E) """ g = collections.defaultdict(list) for u,v in connections: g[u].append(v) g[v].append(u) low = [-1] * n dfn = [-1] * n self.timestamp = 0 res = [] def dfs(cur, parent): if dfn[cur] == -1: dfn[cur] = self.timestamp... [Read More]

class Solution: def calculateTime(self, keyboard: str, word: str) -> int: """tc O(N) N: len(word) sc O(1) main idea: record the index for each character from the keyboard. begin point is idx = 0, loop through the word, get each char's index, add the absolute diff from previous finger's position and... [Read More]

class Solution: def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]: """ tc O(NlgN + N*(N-1)*(N-2)/3! ) sc O(N*(N-1)*(N-2)/3!) 1. sort input by username and timestamp 2. put all the visited sites onto history list by username 3. for each history list, get its combination with size 3 to... [Read More]