Jobs

Interviews

Discussions

Group Shifted Strings

#149 Most AskedMedium

Group Shifted Strings #149 Most Asked

Medium

Uber

5 views

Topics:

Strings

We can shift a string by shifting each of its letters to its successive letter. For example, "abc" -> "bcd". We can keep shifting the string to form a sequence.

For example, given the string "abc", we can obtain the series: "abc" -> "bcd" -> ... -> "xyz".

Given a list of strings, group all strings that belong to the same shifting sequence. You can return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= strings.length <= 200
1 <= strings[i].length <= 50
strings[i] consists of lowercase English letters.

Try coding it in LeetCode

Group Shifted Strings

#149 Most AskedMedium

Group Shifted Strings #149 Most Asked

Medium

Uber

5 views

Topics:

Strings

We can shift a string by shifting each of its letters to its successive letter. For example, "abc" -> "bcd". We can keep shifting the string to form a sequence.

For example, given the string "abc", we can obtain the series: "abc" -> "bcd" -> ... -> "xyz".

Given a list of strings, group all strings that belong to the same shifting sequence. You can return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= strings.length <= 200
1 <= strings[i].length <= 50
strings[i] consists of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings contain characters other than lowercase English letters?
Is the input list of strings guaranteed to be non-empty?
If no strings are shifted versions of each other, should I return an empty list of lists, or is there another expected output?
Can the input list contain duplicate strings, and if so, how should they be handled in the grouping?
Is the order of the groups and the order of strings within each group important in the output?

Brute Force Solution

Approach

The brute force approach involves checking every single pair of words to see if they belong in the same group. Two words belong in the same group if shifting all the letters in the first word by the same amount results in the second word. We compare each word to every other word to determine their group affiliation.

Here's how the algorithm would work step-by-step:

Take the first word from the list of words.
Compare this word to every other word in the list.
To compare, imagine 'shifting' the letters of the first word (e.g., 'abc' shifted once becomes 'bcd'). Figure out the shift needed to transform the first word into the second word.
If the second word can be obtained by shifting the first word, then consider them to be in the same group.
Repeat the process of comparing the first word with all remaining words.
Once you have compared the first word with all other words, repeat the whole process, starting now with the second word in the list.
Continue this process until every word has been compared to every other word, allowing you to identify which words belong together in a group.
Finally, organize the words based on the groups identified during the comparison process.

Code Implementation

def group_shifted_strings_brute_force(strings):
    grouped_strings = []

    for current_string_index in range(len(strings)):
        current_string = strings[current_string_index]
        current_group = [current_string]

        # Compare the current string to all other strings
        for other_string_index in range(current_string_index + 1, len(strings)):
            other_string = strings[other_string_index]

            # Check if the strings are shifted versions of each other
            if len(current_string) == len(other_string):
                shift_value = -1
                is_shifted = True

                # Calculate shift based on the first character
                first_shift = (ord(other_string[0]) - ord(current_string[0])) % 26

                for char_index in range(len(current_string)):
                    current_char = current_string[char_index]
                    other_char = other_string[char_index]

                    calculated_shift = (ord(other_char) - ord(current_char)) % 26

                    if first_shift != calculated_shift:
                        is_shifted = False
                        break

                # If shifted, add to the current group and remove from the main list
                if is_shifted:
                    current_group.append(other_string)
                    strings[other_string_index] = ''

        # Only add non-empty groups
        if current_group:
            grouped_strings.append(sorted(current_group))

    # Handle strings that were marked empty
    remaining_strings = [string for string in strings if string != '']
    for string in remaining_strings:
        grouped_strings.append([string])

    return grouped_strings

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each of the n words in the input list. Inside the outer loop, for each word, it compares it against all other words in the list to determine if they belong to the same group via shifting. This comparison process involves, in the worst case, examining each of the remaining n-1 words. Therefore, the total number of comparisons is approximately n * (n-1), which simplifies to O(n²).

Space Complexity

O(N) – The provided brute force approach implicitly requires storing the groups of shifted strings. In the worst case, each word in the input list could belong to a different group. Therefore, the space required to store these groups scales linearly with the number of words, N, in the input list. This leads to auxiliary space proportional to the input size for storing the resulting groups. Hence the overall space complexity is O(N).

Optimal Solution

Approach

The core idea is to convert each string into a standardized form representing its shifting pattern. We then group strings based on this standardized form, as strings with the same pattern belong to the same group.

Here's how the algorithm would work step-by-step:

For each string, calculate the difference in character value between adjacent characters, treating 'a' as 0, 'b' as 1, and so on.
Handle wrap-around: If the difference is negative, add 26 to make it positive. This ensures 'ba' and 'abc' are seen as shifts of each other.
Represent each string's shift pattern as a sequence of these differences.
Use this pattern sequence as a key in a collection (like a dictionary or map).
Store all strings that share the same pattern sequence under the same key.
Finally, the strings grouped under each key are the shifted string groups you're looking for.

Code Implementation

def group_shifted_strings(strings):
    string_groups = {}

    for current_string in strings:
        shift_pattern = ''
        # Construct the shift pattern for the current string.
        for i in range(1, len(current_string)): 
            difference = ord(current_string[i]) - ord(current_string[i - 1])
            if difference < 0:
                difference += 26
            shift_pattern += str(difference) + ','

        # Use empty string as key if string is empty or single character.
        if not shift_pattern:
            shift_pattern = ''

        # Group strings based on the calculated shift pattern.
        if shift_pattern not in string_groups:
            string_groups[shift_pattern] = []
        string_groups[shift_pattern].append(current_string)

    # Convert the dictionary values into a list.
    return list(string_groups.values())

Big(O) Analysis

Time Complexity

O(n*k) – The outer loop iterates through each of the n strings in the input list. Inside the loop, calculating the shift pattern for a string takes time proportional to the length of the string, which we denote as k (average string length). Hashing the shift pattern and inserting/retrieving from the hashmap takes approximately constant time, so the dominant operation inside the loop is calculating the shift pattern. Therefore the overall time complexity is O(n*k).

Space Complexity

O(N) – The primary auxiliary space is used by the hash map (or dictionary) described in the steps. This hash map stores the shift pattern as the key and a list of strings that match the pattern as the value. In the worst case, all N strings are distinct (have different shift patterns), leading to N entries in the hash map. Thus, the auxiliary space used by the hash map is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input list	Return an empty list as there are no strings to group.
List containing only one string	Return a list containing a list with the single string as it's a group of size one.
List containing strings of varying lengths	The grouping logic should still work correctly as only the shifted character differences are considered.
List containing empty strings	Empty strings should all be grouped together as the shift is always the same (no shift).
Strings containing non-alphabetic characters	Handle by either stripping those characters out or explicitly rejecting such strings based on problem constraints.
Large input list with many long strings	Ensure the character difference calculation and hash key generation is efficient to avoid performance bottlenecks.
Strings that shift to themselves (e.g., 'aaa')	These strings should be grouped together based on the same shifted representation which will be consistent within the group.
Integer overflow when calculating shift difference for large character values	Use modular arithmetic to keep the shift difference within a manageable range preventing overflow.

Null or empty input list

How to Handle:

Return an empty list as there are no strings to group.

List containing only one string

How to Handle:

Return a list containing a list with the single string as it's a group of size one.

List containing strings of varying lengths

How to Handle:

The grouping logic should still work correctly as only the shifted character differences are considered.

List containing empty strings

How to Handle:

Empty strings should all be grouped together as the shift is always the same (no shift).

Strings containing non-alphabetic characters

How to Handle:

Handle by either stripping those characters out or explicitly rejecting such strings based on problem constraints.

Large input list with many long strings

How to Handle:

Ensure the character difference calculation and hash key generation is efficient to avoid performance bottlenecks.

Strings that shift to themselves (e.g., 'aaa')

How to Handle:

These strings should be grouped together based on the same shifted representation which will be consistent within the group.

Integer overflow when calculating shift difference for large character values

How to Handle:

Use modular arithmetic to keep the shift difference within a manageable range preventing overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings contain characters other than lowercase English letters?
Is the input list of strings guaranteed to be non-empty?
If no strings are shifted versions of each other, should I return an empty list of lists, or is there another expected output?
Can the input list contain duplicate strings, and if so, how should they be handled in the grouping?
Is the order of the groups and the order of strings within each group important in the output?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first word from the list of words.
Compare this word to every other word in the list.
To compare, imagine 'shifting' the letters of the first word (e.g., 'abc' shifted once becomes 'bcd'). Figure out the shift needed to transform the first word into the second word.
If the second word can be obtained by shifting the first word, then consider them to be in the same group.
Repeat the process of comparing the first word with all remaining words.
Once you have compared the first word with all other words, repeat the whole process, starting now with the second word in the list.
Continue this process until every word has been compared to every other word, allowing you to identify which words belong together in a group.
Finally, organize the words based on the groups identified during the comparison process.

Code Implementation

def group_shifted_strings_brute_force(strings):
    grouped_strings = []

    for current_string_index in range(len(strings)):
        current_string = strings[current_string_index]
        current_group = [current_string]

        # Compare the current string to all other strings
        for other_string_index in range(current_string_index + 1, len(strings)):
            other_string = strings[other_string_index]

            # Check if the strings are shifted versions of each other
            if len(current_string) == len(other_string):
                shift_value = -1
                is_shifted = True

                # Calculate shift based on the first character
                first_shift = (ord(other_string[0]) - ord(current_string[0])) % 26

                for char_index in range(len(current_string)):
                    current_char = current_string[char_index]
                    other_char = other_string[char_index]

                    calculated_shift = (ord(other_char) - ord(current_char)) % 26

                    if first_shift != calculated_shift:
                        is_shifted = False
                        break

                # If shifted, add to the current group and remove from the main list
                if is_shifted:
                    current_group.append(other_string)
                    strings[other_string_index] = ''

        # Only add non-empty groups
        if current_group:
            grouped_strings.append(sorted(current_group))

    # Handle strings that were marked empty
    remaining_strings = [string for string in strings if string != '']
    for string in remaining_strings:
        grouped_strings.append([string])

    return grouped_strings

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

For each string, calculate the difference in character value between adjacent characters, treating 'a' as 0, 'b' as 1, and so on.
Handle wrap-around: If the difference is negative, add 26 to make it positive. This ensures 'ba' and 'abc' are seen as shifts of each other.
Represent each string's shift pattern as a sequence of these differences.
Use this pattern sequence as a key in a collection (like a dictionary or map).
Store all strings that share the same pattern sequence under the same key.
Finally, the strings grouped under each key are the shifted string groups you're looking for.

Code Implementation

def group_shifted_strings(strings):
    string_groups = {}

    for current_string in strings:
        shift_pattern = ''
        # Construct the shift pattern for the current string.
        for i in range(1, len(current_string)): 
            difference = ord(current_string[i]) - ord(current_string[i - 1])
            if difference < 0:
                difference += 26
            shift_pattern += str(difference) + ','

        # Use empty string as key if string is empty or single character.
        if not shift_pattern:
            shift_pattern = ''

        # Group strings based on the calculated shift pattern.
        if shift_pattern not in string_groups:
            string_groups[shift_pattern] = []
        string_groups[shift_pattern].append(current_string)

    # Convert the dictionary values into a list.
    return list(string_groups.values())

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input list	Return an empty list as there are no strings to group.
List containing only one string	Return a list containing a list with the single string as it's a group of size one.
List containing strings of varying lengths	The grouping logic should still work correctly as only the shifted character differences are considered.
List containing empty strings	Empty strings should all be grouped together as the shift is always the same (no shift).
Strings containing non-alphabetic characters	Handle by either stripping those characters out or explicitly rejecting such strings based on problem constraints.
Large input list with many long strings	Ensure the character difference calculation and hash key generation is efficient to avoid performance bottlenecks.
Strings that shift to themselves (e.g., 'aaa')	These strings should be grouped together based on the same shifted representation which will be consistent within the group.
Integer overflow when calculating shift difference for large character values	Use modular arithmetic to keep the shift difference within a manageable range preventing overflow.

Null or empty input list

How to Handle:

Return an empty list as there are no strings to group.

List containing only one string

How to Handle:

Return a list containing a list with the single string as it's a group of size one.

List containing strings of varying lengths

How to Handle:

The grouping logic should still work correctly as only the shifted character differences are considered.

List containing empty strings

How to Handle:

Empty strings should all be grouped together as the shift is always the same (no shift).

Strings containing non-alphabetic characters

How to Handle:

Handle by either stripping those characters out or explicitly rejecting such strings based on problem constraints.

Large input list with many long strings

How to Handle:

Ensure the character difference calculation and hash key generation is efficient to avoid performance bottlenecks.

Strings that shift to themselves (e.g., 'aaa')

How to Handle:

These strings should be grouped together based on the same shifted representation which will be consistent within the group.

Integer overflow when calculating shift difference for large character values

How to Handle:

Use modular arithmetic to keep the shift difference within a manageable range preventing overflow.

0/495 Uber questions completed

0/495 completed