Review List

3. Longest Substring Without Repeating Characters

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]

21. Merge Two Sorted Lists

recursive

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class 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 = None
class 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