# Review List

## 3. Longest Substring Without Repeating Characters

2 min readApr 10, 2020

--

## 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 = 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