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]

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store