We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Group Shifted Strings

Number: 249

Difficulty: Medium

Paid? Yes

Companies: Meta, Google, Uber, Wix

Problem Description

Given an array of strings, group together all strings that belong to the same shifting sequence. A shifting sequence is defined by the operation where each letter of a string is shifted to its successive letter (with 'z' wrapping around to 'a') or its preceding letter (with 'a' wrapping around to 'z'). For instance, "abc" can be shifted right to "bcd" and "xyz" can be shifted right to "yza". Two strings belong to the same shifting sequence if one string can be transformed into the other by a series of shift operations.

Key Insights

  • All strings in the same group have the same relative differences between adjacent characters.
  • Normalize each string’s pattern by converting it to a key representation based on the differences between consecutive letters.
  • A single character string forms its own group as there are no differences to compute.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of strings and m is the average length of the strings (to compute each string's key). Space Complexity: O(n * m) to store the keys and grouping in the hash table.

Solution

The solution involves iterating over each string and generating a unique key that represents the relative differences between adjacent characters. This key is calculated by computing the difference (mod 26) between every consecutive pair in the string. Strings that share the same key can be grouped together since they can be shifted into one another. A hash table (or dictionary) is used to store and group the strings by their computed key. This approach handles edge cases like single-character strings separately.

Code Solutions

# Python solution for grouping shifted strings

def group_shifted_strings(strings):
    # Helper function to generate a unique key for each string based on differences
    def get_key(s):
        # Single character strings return a fixed key
        if len(s) == 1:
            return "0"
        # Compute differences modulo 26 for each adjacent characters
        key = []
        for i in range(1, len(s)):
            diff = (ord(s[i]) - ord(s[i-1]) + 26) % 26
            key.append(str(diff))
        # Use tuple interleaving or join to form a string key
        return ','.join(key)
    
    groups = {}
    # Group strings by their computed key
    for s in strings:
        key = get_key(s)
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    # Return grouped strings as a list of lists
    return list(groups.values())

# Example usage:
print(group_shifted_strings(["abc","bcd","acef","xyz","az","ba","a","z"]))
← Back to All Questions