Longest Substring Without Repeating Characters Flashcards
https://leetcode.com/problems/longest-substring-without-repeating-characters/?envType=list&envId=rkzwnm95
1
Q
How will you store char?
A
new Set()
- Use Set which is an object that lets you store unique values of any type
2
Q
What variables will you use?
A
- Use start = 0 as pointer
- Use longest = 0 to keep track of longest string
3
Q
How will you loop?
A
- Use for loop and set “end” pointer as variable
- Use while loop to check if set has char
4
Q
What happens if set has char?
A
- Delete char from start pointer
- Increment start
- Add new char from end pointer
5
Q
How is longest constantly being checked/updated?
A
- Reassigning longest through Math.max comparing current longest and pointers end - start + 1
6
Q
What is the time complexity?
A
O(n)
- Even though there is a nested while loop, each character in string is processed only once to add and remove from set
-The overall number of operations is proportional to n, the length of the string
7
Q
What is the space complexity?
A
O(n)
- Worst-case scenario all the characters are unique, so the set will have to store all n characters
