Group Shifted Strings

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

Input: strings = ["a"]
Output: [["a"]]

---

If we're going to group things together, similar to the question Group Anagrams, we can do so by utilizing a HashMap and having the hash key be a common value that the grouping shares.  

If we look at the first two strings, "abc" and "bcd", we may notice a pattern that each consecutive value is the previous value plus one. This means that if we converted both of these two strings to their first shift position, then we would have "abc" and "abc", which can also be viewed as "012" and "012".  Similarly, if we had "efg", "hij", "jkl", all of these would still have an initial first shift position of "abc", or "012".  We found a pattern to hash with. 

To solve this, we can convert each string to its initial shift position by looking at the first character and finding how far its ASCII value is from the letter "a".  That distance will tell us how many times we need to shift each character in the string to convert it.

We'll then group each string by its initial shift position, and these hash values are what we will be returning.

---

Let's start by creating our groups' dictionary and a list for our shifted strings.

        groups, shifted_strings = {}, []

 

We'll also need an output list.

        output = []

 

For each string in the strings array, we'll see how much it has shifted from its initial position by looking at the order of the first character and subtracting that by the order of "a".

            shift = ord(string[0]) - ord('a')

 

Then, we will build a shifted string using that information.

            shifted = []

 

For each character in the string, we will shift it back to its original position by getting its order subtracted by "a", which will let us know its [0,25] order within the English alphabet, and then subtract that order by the shift amount, essentially shifting it back to its first position.

In the scenario that the original string had a decreasing subsequence like "cba", we'll need to modulo the result by twenty-six so that we don't fall outside the order of the alphabet with negative values.  This will basically make it to where we are able to find a relative order for a decreasing subsequence by moving from the end of the alphabet to the beginning, wherein an increasing subsequence we are moving from the beginning of the alphabet to the end.

Once we have shifted the current character, we will append that to the shifted string array.

            for char in string:
                shifted.append(str((ord(char) - ord("a") - shift)%26))

 

When we have shifted each character of the string, we will append that shifted string to the shifted strings array, but first, we'll need to convert it to a tuple since arrays are unhashable data types.

One thing to note here is that the reason we are using tuples instead of strings is that for example, if we had "bc" and "m", that shift result would be "12" and "12" since the single-digit numbers from the first string would be joined together but we can see that grouping these two strings together would be incorrect.

             shifted_strings.append(tuple(shifted))

 

Now that we have a list of shifted strings, we will begin our grouping.

For each string in the shifted strings, we will append the old string to the group of the new string.  This will allow strings with common initial shift values to be grouped together.

        for i, new_string in enumerate(shifted_strings):
            old = strings[i]
            if new_string not in groups:
                groups[new_string] = [old]
            else:
                groups[new_string].append(old)

 

Once we have done that, we just need to append each grouping to the output then return it.

        for grouping in groups.values():
            output.append(grouping)
           
        return output

---