Ace Your Coding Interview- Blind 75 Solved and Explained — Part 5 Strings
This week we explore the topic of strings. String manipulation is one of the most commonly asked questions in interviews. Understanding useful techniques such as frequency arrays and sliding windows are integral to mastering string-related questions.
As always the link to the original Blind 75 is below:
Longest Substring Without Repeating Characters
We require a way to store the character and the index of the character to solve this problem. We can do this in a variety of ways. For this solution, we utilize HashMaps. We can create the same effect using a character array, as you will see in future questions. Other than this, they guide the question towards us linearly, looking through our array and adjusting the maximum length we find.
Our Approach:
- Check if the length of the string is zero—indicating no substring. If so, return 0.
- Create a HashMap storing the character and each of their index's most recent indices.
- Next, we loop through the string and fill up our HashMap. During this process, we track variable j pointing to the last character index in the longest substring.
- To fill our HashMap, we check if the map contains the string we are currently on. If the character is found previously, thus in the HashMap, we update our variable j.
- If a character isn’t found, we add it to our HashMap so it can be seen in future iterations.
- Update the length of the longest substring by comparing the previous max value to the current length.
- Return the length of the max string.
Longest Repeating Character Replacement
This question introduces us to a key concept we will use across several questions: the frequency array. It is simply a character array storing the frequency of each letter in the alphabet found in the string.
Our Approach:
- Wedeclare the following variables:
left: the left pointer
count: the map for counting the frequency of characters
max: the longest repeating character replacement value
most_freq: the character with the highest frequency - After we declare our variables, we traverse our string. Through this traversal, we declare our iteration variable to be right and utilize this as our right pointer.
- After we enter our pointer, we take the value of our current letter and iterate our frequency map. What this means is the following: we can subtract ‘A’ from our current character to see its numerical value in the alphabet. We would then index this value and increase it by one.
- We find our most frequent character. This is done simply by comparing our current character’s frequency to what the previous most_freq value was and adjusting most_freq as needed.
- Next, we identify how many characters to replace. This process is as follows. Find the length of our current substring, which is simply the position of our right pointer minus the position of our left pointer plus one. Since we know how long our string is we can take this value and subtract our most_freq value to see how many new characters we would need.
- If the characters needed to be replaced surpass the k value provided to us, increment left and decrement the count of characters at the left pointer. This way we are pushing our left pointer forward to not account for the previous character, which wasn’t feasible.
- Otherwise, if the characters needed are less than or equal to k, we can adjust our longest repeating character replacement value by comparing our total to the current maximum.
- Finally, return max.
Minimum Window Substring
The name of this question gives us a good idea of how to approach it — a sliding window. Normally, we find ourselves expanding a window to fit our needs. On the contrary, for this question, we have our window contain the entire string and shrink the window from the beginning and the end to find the best fit. We will first approach from the end, shrinking our string until it has all the characters we need from the back side. Then we go to the beginning of the string and optimizing it from the front side.
Our Approach:
- As before, we set up our frequency map to store the frequency of each character. However, this time we fill it up with string t. This way, we can track the frequency of needed characters in the string to achieve the minimum window.
- We are also going to declare a few pointers. The head and tail will point towards the head and tail of our minimum substring. Begin and end will point toward our location in the string as we are traversing it. We also need a counter to show us how many characters are left to find.
- Next, we traverse our word. We can keep proceeding with our traversal as long as the end pointer doesn’t surpass the length of the list–which would indicate out of bounds.
- Since we aim for a minimum window size, we start from the largest string first and shrink from the beginning and end until we reach our goal. First, we cache our current end character and then progress our end pointer forward.
- If our cached character exists within our frequency map we can decrement our counter and map by once. When the frequency of a character is zero on our map this shows us that a character has been found.
- We continue this operation until our counter hits zero, meaning we found all the characters we were looking for. At this point, we transition to the beginning of the word and progress from there.
- We check if the current word we found has a length shorter than the previous one. This is simply done by taking the end and subtracting it from the beginning. If that is the case, we update the head and tails as well to reflect the new shortest string positions.
- We do the same operations as previously done on the end to the beginning pointer. We cache the begin pointer's current character value and move the pointer forward. Next, we check if the cached value exists in the frequency map. If it doesn’t, we can update our counter to increment by one. Finally, we increment our cached value pointer by one.
- When done with the while loop, return the substring starting at the head and finishing at the tail.
Is Anagram
An Anagram is a word where the letters in each word occur at the same frequency. This means by simply utilizing a frequency map and keeping track of the number of times each letter occurs, we can find a solution to this question.
Our Approach:
- Declare a character array to store the frequency of each character in the string
- Loop through the first string and update the frequency of each character by incrementing them by one.
- Next, we loop through the second string and decrement the frequency of each character. In an anagram, since the frequency of the characters must be equal by the end of this process, all our values should be zero.
- We iterate through our frequency map and check if any values are not equal to zero. If a value is not equal to zero, that indicates we don’t have an anagram.
- If all iterations pass, meaning we had all zeros, we have an anagram, which returns true.
Group Anagrams
Since we know anagrams have the same frequency of each letter we can once again use this to our advantage. If we sort two words that are anagrams, they must equal each other. This way we can group all our anagrams onto a HashMap. By storing them as values into HashMap we group all the anagrams onto a key that is their sorted version.
Our Approach:
- We require two declarations:
The list of lists to store our results.
HashMap to store a list of anagrams. - We iterate through the string array and perform the following set of operations on each string.
- Like the previous question, the important part of anagrams is the frequency of letters. So we will sort each string’s characters and assign it to a sorted string. We will do this by utilizing a simple helper function that breaks the string down to a character array, sorts the array, and returns the array in the format of a string.
- Since we now possess a sorted word, we check if the word exists in our HashMap. If contained, we add the unsorted word into the HashMap as a value under the key of the sorted word.
- If not contained, we create a new list containing the current unsorted word. Then we add the list into our HashMap with the sorted string as our key value.
- After we finish looping through our strings array, we traverse our HashMap and add the values to the results list.
- Return the list of anagrams.
Is Valid Parentheses
For me, the hardest part of the question was understanding the best data structure to use/approach. I’ve come to find the stack to be extremely useful. The push and pop methods make it easy when we understand the last parentheses is the first one out — LIFO.
Our Approach:
- Create a stack to hold our characters since each opening of a parenthesis needs a closing. This data structure works very well utilizing its push and pop methods. Not only that, but stacks utilize a last in first out structure. This way, the element on the top is the most recent.
- We iterate through each element as a character by converting the string to a character array and looping through it.
- As we loop, we check if any sort of parentheses opening is occurring. If that is the case we add the closing to that type of parentheses into our stack. We do this so we can pop it as we start checking the closing parentheses.
- If we are not looking at opening parentheses, the parentheses must be closing one. So we pop the top of the stack. If the top of the stack is not equal to the closing parentheses in the stack, we conclude that the parentheses are not valid.
- By the end of our operation, if our stack is empty, we know we have checked all opening and closing parentheses. Return if the array is empty.
Valid Palindrome
A palindrome indicates that a word is spelled the same forward and backward. This is a pretty popular question in the coding world. The only big difference to account for is the fact that we have to address characters that aren’t valid digits or letters.
Our Approach:
- Convert all our characters to the same case. So we can get rid of the difference between upper and lowercase letters.
- Next, we convert our string to a character array so we can traverse through each character individually.
- We declare a left and right pointer. This is because for a palindrome to be true the word must be a mirror of itself when divided in the middle, so by using left and right pointers we can check the middle of the list at the same time as the end of the list.
- Create a while loop that occurs until the left pointer is less than the right pointer. When the left is larger than the right it means we have crossed the middle point in our array, thus no new characters can be found.
- The next two operations occur so we can get rid of any characters that don’t concern us — these include anything that isn’t a letter or digit. So the next motion we decrement the right pointer until we find a valid character. On the other hand, we increment the left pointer until we find a valid character. During these operations, we also keep in mind if at any point we cross the middle point when the left crosses over the right.
- We check if the characters at two pointers are equal, if they aren’t this indicates it is not valid for a palindrome.
- If we manage to get out of our loop when left crosses right this means no characters had mismatches, indicating we found a valid palindrome.
Longest Palindromic Substring
Since palindromes are spelled the same backward and forwards this means they are mirrors from the centers. So if we were to start from the center and expand outwards we can find the longest palindromes possible
Our Approach
- Check the case where our string is null or has characters at which point we return an empty string.
- As with finding palindromes before we declare left and right pointers to check the different characters.
- Next, we iterate through our string until we reach the end. Through each iteration, we find the longest palindromic expansion.
- For each palindrome, we utilize the following method to find the length of the longest possible palindrome. We use a method called “expandAroundCenter” for this purpose.
a. This method will receive a string as well as a left and right pointer.
b. The left and right pointers in this case are going to be used depending on if we are looking for an even or odd palindrome. If the left and right pointer are given the same value we are looking at odd length palindrome since they are expanding from the same source. If they are different this would indicate even length.
c. Next, we have to create the operation of expanding around the center. We check if our left pointer is greater than or equal to zero and check if our right pointer is less than the length of our string. We check if our left pointer and right pointer have the same value. While these statements are all true we decrement left and increment right, hence, the expansion around the center.
d. Return the length of the string by subtracting left from right and adding one. - After we have found the lengths for the even and odd lengths, we see which of these strings were longer.
- Before we finish our while loop we update our left and right pointer. We check if the length of our current string surpasses our current length — right minus left. For the left pointer, we take our index and subtract our length minus one from it. For the right pointer, we take our current index and add half the length to it. This way we used our current index as our middle point and expanded outwards from the selected point.
- Finally, return the substring of the longest palindromic substring.
Palindromic Substring
This is almost identical to our previous question. The major difference is we count the number of palindromes we find. We will utilize the same expansion algorithm as the previous question with one adjustment. Each expansion indicates another count of palindromes. As we expand we go up to the longest palindrome but the longest palindrome contains many other palindromes within.
Our Approach:
- We declare a count to track all the palindromes we find.
- Traverse the string from the beginning to the end. As we are traversing we initiate our expansion around the center method that was used in our previous question.
- We check for both odd and even length palindromes to do this we take our current index as the center point and use our ‘expandAroundCenter’ method. To check for odd lengths we set our index as both the left and right argument. For even length, we are going to set index as our left and index plus one as the right argument. This is so we can expand from a center of 2 values versus one.
- We utilize the same method in the question above with a few minuscule changes. This time the method will be returning the number of palindromes that are found. We keep track of the count of palindromes and every time we can expand that indicates we found a new palindrome so we just increment the value of the count. Once we can no longer expand we return the number of valid expansions — also the number of palindromes found.
Posts in the Series
Trees Part 2: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-6-2-trees-continued-64cf6f60350
Dynamic Programming: Coming Soon
Graph: Coming Soon