# Review List

## Naive solution O(n³) TLE

986 / 987 test cases passed. NOT THAT BAD

`class Solution:    def lengthOfLongestSubstring(self, s: str) -> int:        if not s:return 0        for l in range(len(s), 0, -1):            for i in range(len(s)):                if len(set(s[i:i+l]))==l:return l`

## Binary search Time complexity O(n² log n) (9840 ms)

`class Solution:    def lengthOfLongestSubstring(self, s: str) -> int:        if not s:return 0        def binary_search():            l, r = 1, len(s)            def good(m):                for i in range(len(s)):                    if len(set(s[i:i+m]))==m:return True                return False            while l<r:                m = (l+r+1)//2                if good(m):                    l = m                else:                    r = m-1            return l        l = binary_search()        return l`

Optimal solution

The solution is from here

`class Solution:    def lengthOfLongestSubstring(self, s: str) -> int:        used = {}        max_length = start = 0        for i, c in enumerate(s):            if c in used and start <= used[c]:                start = used[c] + 1            else:                max_length = max(max_length, i - start + 1)                        used[c] = i        return max_length`

## 819. Most Common Word

`class Solution:    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:        banned = set(banned)        words = [word for word in re.findall(r"([a-z]+)",  paragraph.lower()) if word not in banned]        #print(words)        cnt = collections.Counter(words)        return max(cnt.items(), key=lambda x:x[1])[0]`

## recursive

`# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        def helper(l1, l2):            if l1 is None:return l2            if l2 is None:return l1            if l1.val>l2.val:                l2.next = helper(l1, l2.next)                return l2            else:                l1.next = helper(l1.next, l2)                return l1        return helper(l1, l2)`

## iterative

`# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        dummy = ListNode(-1)        if not l1 and not l2:return None        node = dummy        while l1 and l2:            if l1.val<l2.val:                node.next = l1                l1 = l1.next            else:                node.next = l2                l2 = l2.next            node = node.next        node.next = l1 or l2        return dummy.next`

--

--

## More from Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.