Following is a solution shared with the subscribers of the newsletter. To gain access to more such solutions and join programmers/software developers acing their coding and system design interviews, check out the subscribe to the newsletter here:
Problem
This problem was asked by Facebook.
Given an array of strings (all lowercase letters), the task is to group them in such a way that all strings in a group are shifted versions of each other. Two string S and T are called shifted if,
S.length = T.length
and
S[i] = T[i] + K for
1 <= i <= S.length for a constant integer K
For example strings, {acd, dfg, wyz, yab, mop} are shifted versions of each other.
Step 1: Understanding the Ask
Problems such as this can be very confusing at first. This is because it’s very easy to view them as comparison problems (where we have to compare two or more strings with each other). This is more of a grouping problem. We want to group shifted strings together. This leads to a natural problem. How we know what the strings are shifted by?
An easy is to loop through the string and look at the difference b/w consecutive characters. Each difference can be appened to a string. For example, the string “fgd” would have the corresponding string, “21”. We’ll call this string the difference string. When implementing this, remember to consider the case where we have a wraparound. Would the difference for “za” be 1 or -25 (or something else entirely)? Whatever you choose, make sure to spell it out clearly to show your ability to consider the edge cases.
We have now reframed this as: group the sets by the difference string. Assuming that we could create a difference string for any string input, is there a data structure that can group them by their respective difference string? Furthermore, we want a data structure that will be able to have quick retrieval, since we want to look at the difference string multiple times.
Step 2: Enter the HashSet
Anytime your problem involves a lot of looking, and grouping by a unique key, think of a hashset. They have constant lookup, so it’s cheap to see if a key exists or to modify the values associated with a key.
So what would the hashset look like? The key will be the difference string. The value will be a list of all the strings with that difference string. See how close that gets us to the solution? Our solution will conceptually look like this:
groups=dict()
for str in strings:
diff=diffString(str) #to be implemented later
if diff in groups:
groups[diff].append(str)
else:
groups[diff]=[str]
return groups
Now the final piece of the puzzle is implementing the diffString protocol. How do we do that?
Step 3: Diff String
As a general rule, you want to use helper functions when you can. The benefits are many:
They let you put off implementing harder/different things till later while solving the problem. This is crucial to smoothly interviewing/coding.
Shows your ability to organize and be methodical in your answers
Makes your solutions much neater.
What should our diffString solution look like? We know it takes a string as input, and returns another one. Since we have to consider the difference between consecutive pairs of chars, we loop through the string. Putting things together it looks like:
def getDiffString(s):
shift=""
for i in range(1, len(s)): # we start at 1 not 0
dif = (ord(s[i]) -
ord(s[i - 1]))
if(dif < 0):
dif += 26 #"za" gives 1
# Representing the difference
# as char
shift += str(dif) #Remember to cast your difference to strign
# This string will be 1 less
# length than str
return shift
Step 4: Combining it all
To finally combine the solution we get:
def getDiffString(s):
shift=""
for i in range(1, len(s)): # we start at 1 not 0
dif = (ord(s[i]) -
ord(s[i - 1]))
if(dif < 0):
dif += 26 #"za" gives 1
# Representing the difference
# as char
shift += str(dif) #Remember to cast your difference to strign
# This string will be 1 less
# length than str
return shift
def groupShiftedString(str,n):
groupMap = dict()
for i in range(n):
diffStr = getDiffString(str[i])
if diffStr not in groupMap:
groupMap[diffStr] = [i]
else:
groupMap[diffStr].append(i)
return groupMap
What are the time and space complexities of this solution:
Time
We loop through the list of input strings. Additionally each string is looped through. If the length of the list is n and the average length of the strings in the list is m, we have the complexity O(n*m). Since lookup and insertion is constant time in hashets, they don’t add too much more.
Space
We store the list of input strings. Additionally each string has a diff string that is stored as a key. If the length of the list is n and the average number of the diff-strings in the list is m, we have the complexity O(n+m).
Final: Time- O(n*m) and Space- O(n+m)
If you liked this solution, make sure you subscribe to the newsletter for more such content.
Bonuses/Promotion (Get Free Stuff)
Have anything to say to me? Use the links below.
To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.
To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:
Reach out to me on Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/