Leetcode: Strings Flashcards
- Longest substring with repeating characters
Given a string s, find the length of the longest substring without repeating characters.
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
Double for loop is brute force.
- Dictionary to get linear time key, value = letter, index
- Sliding window, need a variable to account for the beginning of the sliding window, for loop handles tail end
- Calculate length on each iteration
- Modify sliding window each time a letter is already in the dictionary and key-value is greater than the start index
- Update the key-value per letter each loop
- Need a <= comparison for the start/usedChar dictionary so it triggers on “a…a” and doesn’t count “a” twice
Time = O(N) Space = O(26), constant since we have 26 characters in the alphabet
class Solution:
- —def lengthOfLongestSubstring(self, s: str) -> int:
- ——-seen = {}
- ——-ans = 0
- ——-start = 0
- ——-for i, x in enumerate(s):
- ———–if x in seen and start <= seen[x]:
- —————start = seen[x] + 1
- ———–else:
- —————cur = i - start + 1
- —————ans = max(ans, cur)
- ———–seen[x] = i
- ——-return ans
Falling dominos
Given a string with the initial condition of dominoes, where:
. represents that the domino is standing still
L represents that the domino is falling to the left side
R represents that the domino is falling to the right side
Figure out the final position of the dominoes. If there are dominoes that get pushed on both ends, the force cancels out and that domino remains upright.
dominos = "..R..LL..R." answer = ..RRLLL..RR
you can do this in a very methodical way in which you get 2 lists of left and rights, then once you get the lists you can iterate through them to create a final list by going right, then left
- KEY!! understand forcing functions in code. Using indexes and a trigger of the force, the initial index is equal to max_force, then each index after you subtract 1 from the force.
- If there is an opposing force, then you do the opposite in the opposite range(len(list)-1, -1, -1)
- This will ultimately end up with when the forces collide, the superior force will either be 0 (neutral) positive (forward force) negative (backwards force)
- if a forward-facing force meets the index of a backwards-facing force, the forward force becomes 0
time: O(n), 3n because we loop through it forward, backwards, and again to make the final string
space: O(n), 2n because we have the force list and the response list. response list helps us reduce the string appending to linear time vs quadradic (confirm with documentation)
class Solution:
- —def answer(self, n):
- ——-force = [0]*len(n)
- ——-f=0
- ——-for i in range(len(n)):
- ———–if n[i]==”R”:
- —————f=len(n)
- ———–elif n[i]==”L”:
- —————f=0
- ———–else:
- —————f=max(0, f-1)
- ———–force[i]+=f
- ——-fl=0
- ——-for i in range(len(n)-1, -1, -1):
- ———–if n[i]==”L”:
- —————fl=-len(n)
- ———–elif n[i]==”R”:
- —————fl=0
- ———–else:
- —————fl=min(fl+1, 0)
- ———–force[i]+=fl
- ——-response=[]
- ——-for x in force:
- ———–if x>0:
- —————response.append(“R”)
- ———–elif x<0:
- —————response.append(“L”)
- ———–else:
- —————response.append(“.”)
- ——-return ““.join(response)
list strategies for strings
- two pointers are a good idea if the list or string is sorted
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Example 1:
Input: s = “leetcode”
Output: 0
Example 2:
Input: s = “loveleetcode”
Output: 2
class Solution:
- —def firstUniqChar(self, s: str) -> int:
- ——-m={}
- ——-for i, x in enumerate(s):
- ———–if x not in m:
- —————m[x]=False
- ———–else:
- —————m[x]=True
- ——-for i,x in enumerate(s):
- ———–if not m[x]:
- —————return i
- ——-return -1
time: O(n), double loop,
space: O(26), constant time bc we use a hashmap with alphabet keys
validate parenthesis
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order
- haspmap + stack
- create a map with k/v as the opening/closing of the brackets
- if item in hashmap, add it to stack, else check if stack has items, then pop the last item off thestack and compare it to the k/v pair of the current item.
- to be valid, at step 3 they have to be equal
- if the stack has items in it at the end, it is also false so check for that
time: linear
space: linear
class Solution:
- —def fav(self, s):
- ——-_map={“{“: “}”, “(“: “)”, “[”: “]”}
- ——-stack=[]
- ——-for i in s:
- ———–if s in _map:
- —————stack.append(s)
- ———–elif not stack or _map[stack.pop()]!=i:
- —————return False
- ——-return not stack
- —def reverse(self, s: str) -> bool:
- ——-_map={“}”: “{“, “)”: “(“, “]”: “[”}
- ——-stack=[]
- ——-for i in s:
- ———–if i in _map:
- —————if not stack:
- ——————-return False
- —————if stack and stack.pop()!=_map[i]:
- ——————-return False
- ———–else:
- —————stack.append(i)
- ——-return not stack
generate parenthesis
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
brute force is to get all possible permutations, check if they are valid, then return the valid ones. Returning the cartesian products (permutations) of N items with a total length of S is N^S. time and space are 2^(2N) here
class Solution:
- —def brute(self, n: int):
- ——-s=”()”
- ——-temp=set()
- ——-for p in itertools.product(s, repeat=n*2):
- ———–temp.add(““.join(p))
- ——-output=[]
- ——-for x in temp:
- ———–if self.validate(x):
- —————output.append(x)
- ——-return output
- —def validate(self, s):
- ——-_map={“(“:”)”}
- ——-stack=[]
- ——-for i in s:
- ———–if i in _map:
- —————stack.append(i)
- ———–elif not stack or _map[stack.pop()]!=i:
- —————return False
- ——-return not stack
- backtracking
- to build a valid parenthesis, the opening brackets must be equal to n, same with closing, and there can never be more closing than opening at any time
- backtracking means that if we move forward with a step and it does not work, we can easily go backwards.
- to do this, we check if openings
time: O(4^n / n^0.5) Catalan number, which is 4^n / (n^1.5), and for each iteration, we have to append something of N length, so it increases it to 4^n / n^0.5. Realistically, if you gave 2^2n * n it would be acceptable.
space: same as above, we must store each answer which is the catalan number, and each catalan number is N length so multiply them you get O(4^n / n^0.5)
- —def generateParenthesis(self, n):
- ——-self.answer = []
- ——-self.backtrack([], 0, 0, n)
- ——-return self.answer
- —def backtrack(self, current, openings, closings, n):
- ——-if len(current) == 2*n:
- ———–self.answer.append(““.join(current[:]))
- ——-else:
- ———–if openings [less than] n:
- —————current.append(“(“)
- —————self.backtrack(current, openings+1, closings, n)
- —————current.pop()
- ———–if closings [less than] openings:
- —————current.append(“)”)
- —————self.backtrack(current, openings, closings+1, n)
- —————current.pop()
Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
brute force/intuition is backtracking
- BACKTRACKING
- make hashmap of number/letter combos
- the backtracking method takes the current index of the input string and the current list
- each method loops through its respective letter combinations, so if input=”23”, the first method only loops through “2” letters
- stop when len(current)=len(digits) or index>=len(digits)
- don’t forget to wrap in an if/else since the backtracking basecase doesn’t return anything
time: O((4^n)*N), worst case of 7/9s we have 4 choices for each digit, and at each combination we need to concatenate the current to the output which takes N time
space: O(n) not including the output or the hashmap since that is constant, we care about the recursion tree height which is only ever N
class Solution:
- —def letterCombinations(self, digits):
- ——-if not digits:
- ———–return []
- ——-self.hashmap={“2”: [‘a’, ‘b’, ‘c’],
- —————“3”: [‘d’, ‘e’, ‘f’],
- —————“4”: [“g”, “h”, “i”],
- —————“5”: [“j”, “k”, “l”],
- —————“6”: [‘m’, ‘n’, ‘o’],
- —————“7”: [‘p’, ‘q’, ‘r’, ‘s’],
- —————“8”: [‘t’, ‘u’, ‘v’],
- —————“9”: [‘w’, ‘x’, ‘y’, ‘z’]}
- ——-self.output=[]
- ——-self.helper([], digits, 0)
- ——-return self.output
- —def helper(self, current, digits, index):
- ——-# could just do len(current)=len(digits) you idiot
- ——-if index[greater than]=len(digits):
- ———–self.output.append(““.join(current))
- ——-else:
- ———–num = digits[index]
- ———–for l in self.hashmap[num]:
- —————current.append(l)
- —————self.helper(current, digits, index+1)
- —————current.pop()
Score of parentheses
Given a balanced parentheses string s, return the score of the string.
The score of a balanced parentheses string is based on the following rule:
”()” has score 1.
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.
Example 1:
Input: s = “()”
Output: 1
Example 2:
Input: s = “(())”
Output: 2
Example 3:
Input: s = “()()”
Output: 2
Example 4:
Input: s = “(()(()))”
Output: 6
brute force is a crazy divide and conquer, N^2 time and N space for the recursion stack
class Solution:
- —def brute(self, s: str) -[greater than] int:
- ——-return self.helper(0, len(s), s)
- —def helper(self, start, stop, s):
- ——-ans = bal = 0
- ——-for i in range(start, stop):
- ———–bal += 1 if s[i] == “(“ else -1
- ———–if bal == 0:
- —————if i - start == 1:
- ——————-ans += 1
- —————else:
- ——————-ans += 2 * self.helper(start + 1, i, s)
- —————start = i + 1
- ——-return ans
time: O(n)
space: O(n) bc of the stack, could get n sized
- —def whatIwouldGet(self, s: str) -[greater than] int:
- ——-stack = [0]
- ——-for x in s:
- ———–if x == “(“:
- —————stack.append(0)
- ———–else:
- —————value = stack.pop()
- —————stack[-1] += max(2 * value, 1)
- ——-return stack[-1]
time: O(n)
space: constant
- —def optimal(self, s: str) -[greater than] int:
- ——-ans = bal = 0
- ———–if x == “(“:
- —————bal += 1
- ———–else:
- —————bal -= 1
- —————if s[i-1] == “(“:
- ——————-ans += 1 [less than][less than] bal
- ——-return ans
Valid palindrome
(string includes non-alpha-numeric characters, we need to ignore those)
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
brute is to check if the reversed string is the same as original after we lowercase everything and remove the non-alphanumeric ones, with linear time and space
- 2 pointers
- while right >= left for main, then each pointer gets a while loop until the char.isalnum() returns True (is ABC 0-9) and right > left. it cannot be right >= left because if 1=1, then we subtract, right = 0 and left = 1, bad!
time: O(N) where N is s
space: cosntant
class Solution:
- —def isPalindrome(self, s: str) -[greater than] bool:
- ——-left, right = 0, len(s) - 1
- ——-while right [greater than]= left:
- ———–while right [greater than] left and not s[right].isalnum():
- —————right -=1
- ———–while right [greater than] left and not s[left].isalnum():
- —————left += 1
- ———–if s[left].lower() != s[right].lower():
- —————return False
- ———–left += 1
- ———–right -= 1
- ——-return True
- —def brute(self, s: str) -[greater than] bool:
- ——-lower = [x.lower() for x in s if x.isalnum()]
- ——-return list(lower) == lower[::-1]
palindrome number
Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.
brute force is convert to string, see if s == s[::-1]
- recreated the integer backward
time: Log base 10 (N), you can also say it is linear with respect to the number of 10’s that can be divided into it, but log10(N) probably sound smarter
space: constant
class Solution:
- —def isPalindrome(self, x: int) -[greater than] bool:
- ——-# need this check for anything that ends in 0, like 10 or 100
- ——-if x [less than] 0 or (x % 10 == 0 and x != 0):
- ———–return False
- ——-response = 0
- ——-final = x
- ——-while final [greater than] response:
- ———–response = response * 10 + x % 10
- ———–x //= 10
- ——-return final == response
- —def brute(self, x):
- ——-if x [less than] 0:
- ———–return False
- ——-s = str(x)
- ——-return s == s[::-1]
Implement strStr():
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
Example 1:
Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1
brute force is to do O(n * (m - n)) where m and n are haystack/needle. This makes sure that you are never going out of index of the haystack. hay = 5, needle = 3, 5 - 3 = 2, but that means we only get 0 and 1 indexes, if it is aabcd and bcd, then we miss it, so we add 1 (standard index subtraction to make sure we don’t lose an index)
https://www.youtube.com/watch?v=GTJr8OvyEVQ
time: O(n * (m - n))
space: constant
- —def brute(self, haystack, needle):
- ——-for i in range(len(haystack) - len(needle) + 1):
- ———–if haystack[i: i + len(needle)] == needle:
- —————return i
- ——-return -1
https: //www.youtube.com/watch?v=GTJr8OvyEVQ
1. KMP, memorize it!
2. make sure to check edge cases, bc KMP does not check if they are none and such
time: O(haystack + needle). KMP requires us to make the longest proper suffix (LPS) array which is needle, then the search takes haystack time
space: O(needle) for the LPS array
class Solution:
- —def strStr(self, haystack: str, needle: str) -> int:
- ——-if not needle:
- ———–return 0
- ——-if not haystack:
- ———–return -1
- ——-n = len(needle)
- ——-h = len(haystack)——–
- ——-kmp_arr = [0]*n——–
- ——-needle_pointer = hay_pointer = 0——–
- ——-self.make_kmp_helper(kmp_arr, needle)
- ——-while hay_pointer < h:
- ———–if haystack[hay_pointer] == needle[needle_pointer]:
- —————needle_pointer += 1
- —————hay_pointer += 1
- ———–if needle_pointer == n:
- —————return hay_pointer - needle_pointer
- ———–# we increement np and hp on success, checking to make sure we do not double dip
- ———–if hay_pointer < h and haystack[hay_pointer] != needle[needle_pointer]:
- —————if needle_pointer != 0:
- ——————-needle_pointer = kmp_arr[needle_pointer - 1]
- —————else: #np is 0, start over
- ——————-hay_pointer += 1
- ——-return -1
- —def make_kmp_helper(self, arr, needle):
- ——-n = len(needle)
- ——-start, i = 0, 1
- ——-while i < n:
- ———–if needle[start] == needle[i]:
- —————start += 1
- —————arr[i] = start
- —————i += 1
- ———–else:
- —————if start != 0:
- ——————-start = arr[start - 1]
- —————else:
- ——————-arr[i] = start
- ——————-i += 1
- Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”
- vertical search is intuitive once you realize you can compare it against any arbitrary string, the first string being the easiest
- on a failure during the loop we are finished so return, worst case when every word is the same we need a regular return
time: O(S ) where S is the total length of characters, you could also say O(S * L) where S is the length of the string list and L is the length of the longest string,
space: constant
class Solution:
- —def vertical_search(self, strs):
- ——-prefix = []
- ——-first = strs[0]
- ——-for i in range(len(first)):
- ———–for j in range(1, len(strs)):
- —————if i >= len(strs[j]) or first[i] != strs[j][i]:
- ——————-return ““.join(prefix)
- ———–prefix.append(first[i])
- ——-return ““.join(prefix)
- when you find and it is not equal to 0, we slice the string and try again until we find Y in X at index 0 X.find(Y), this will tell us they have an equivalent prefix
- Once we the longest prefix for X and Y, X and W can only have a smaller or equal one
time: O(S ) where S is the total length of characters, you could also say O(S * L) where S is the length of the string list and L is the length of the longest string,
space: constant
- —def horizontal_search(self, strs):
- ——-prefix = strs[0]
- ——-for j in range(1, len(strs)):
- ———–while strs[j].find(prefix) != 0:
- —————prefix = prefix[:-1]
- —————if not prefix:
- ——————-return “”
- ——-return prefix
reverse a string
time: O(N), N/2 actually
space: constant, recursive is N/2
class Solution:
- —def recursive(self, s):
- ——-self.helper(0, len(s) -1 , s)
- —def helper(self, left, right, s):
- ——-if right > left:
- ———–s[left], s[right] = s[right], s[left]
- ———–self.helper(left + 1, right - 1, s)
- —def iterative(self, s):
- ——-left, right = 0, len(s) - 1
- ——-while right > left:
- ———–s[left], s[right] = s[right], s[left]
- ———–left += 1
- ———–right -=1
- —def slicing(self, s):
- ——-‘’’
- ——-start, stop, step. you could do s[len(s):-1]
- ——-‘’’
- ——-return s[::-1]
reverse words in string
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = “the sky is blue”
Output: “blue is sky the”
Example 2:
Input: s = “ hello world “
Output: “world hello”
Explanation: Your reversed string should not contain leading or trailing spaces.
brute is to use factory methods, linear time and space
from collections import deque
class Solution:
----def factory(self, s):
--------return " ".join(reversed(s.split()))
--------'''
--------s ="b".join("ac") = abc
--------s ="b".join("a") = a
--------print(s)
--------'''
- state machine, in word vs out of word
- add spaces dynamically to response so we don’t need to do it later
- after loop check if we are in the word, if so perform same action as above
time: O(N), where N is the size of s
space: O(N)
- —def optimized_linear_solution(self, s):
- ——-if not s:
- ———–return “”
- ——-response = deque()
- ——-start = 0
- ——-in_word = False
- ——-for i in range(len(s)):
- ———–if s[i] != “ “:
- —————if not in_word:
- ——————-start = i
- ——————-in_word = True
- ———–elif in_word:
- —————response.appendleft(s[start:i])
- —————in_word = False
- ——-if in_word:
- ———–response.appendleft(s[start:])
- ——-return “ “.join(response)
I got this my first try! worked and everything, but not optimized bc we add spaces after the fact instead of during
- —def linear_not_optimized(self, s):
- ——-if not s:
- ———–return “”
- ——-response = deque()
- ——-start = 0
- ——-in_word = False
- ——-for i in range(len(s)):
- ———–if s[i] != “ “:
- —————if not in_word:
- ——————-start = i
- ——————-in_word = True
- ———–elif in_word:
- —————response.appendleft(s[start:i])
- —————in_word = False
- ——-if in_word:
- ———–response.appendleft(s[start:])
- ——-response2 = []
- ——-for j in range(len(response)):
- ———–if j == len(response) - 1:
- —————response2.append(response[j])
- ———–else:
- —————response2.append(response[j] + “ “)
- ——-return ““.join(response2)
reverse words in a string 3
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: s = “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
time/space are linear. the iteration takes N time, the reverse will add N time as well, then appending to the response list is N time.
from collections import deque class Solution: ----def factory_methods(self, s: str) -> str: --------return " ".join([w[::-1] for w in s.split()])
- —def reverseWords(self, s: str) -> str:
- ——-self.response = []
- ——-self.s = s
- ——-start = stop = 0
- ——-for i in range(len(s)):
- ———–if s[i] == “ “:
- —————self.reverse(start, i)
- —————start = i + 1
- ——-self.reverse(start, len(s))
- ——-return “ “.join(self.response)
- —def reverse(self, start, end):
- ——-word = deque()
- ——-for i in self.s[start:end]:
- ———–word.appendleft(i)
- ——-self.response.append(““.join(word))
