Group Shifted Strings - Practice Coding Problems

Group Shifted Strings - Problem

Given an array of strings strings, group together all strings that belong to the same shifting sequence.

A shifting sequence is formed by applying shift operations on a string:

Right shift: Replace every letter with the successive letter of the English alphabet, where 'z' is replaced by 'a'. For example, "abc" → "bcd", "xyz" → "yza"
Left shift: Replace every letter with the preceding letter of the English alphabet, where 'a' is replaced by 'z'. For example, "bcd" → "abc", "yza" → "xyz"

Strings in the same shifting sequence can be transformed into each other through these operations. For example, "abc", "bcd", and "xyz" all belong to the same shifting sequence because:

"abc" → "bcd" → "cde" → ... → "xyz"

You may return the answer in any order.

Input & Output

Example 1 — Basic Grouping

$ Input: strings = ["abc","bcd","acf","xyz","az","ba","a","z"]

› Output: [["abc","bcd","xyz"],["acf"],["az","ba"],["a"],["z"]]

💡 Note: "abc", "bcd", "xyz" have same pattern [1,1]. "az" and "ba" have same pattern [25]. Single characters form separate groups.

Example 2 — All Same Group

$ Input: strings = ["a","b","c"]

› Output: [["a","b","c"]]

💡 Note: All single characters have empty pattern [], so they belong to same group.

Example 3 — Wraparound Pattern

$ Input: strings = ["za","yb"]

› Output: [["za","yb"]]

💡 Note: Both have pattern [1]: 'z'→'a' is +1 (wrapping), 'y'→'b' is +3, but we normalize by taking mod 26.

Constraints

1 ≤ strings.length ≤ 200
1 ≤ strings[i].length ≤ 50
strings[i] consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Calculate difference pattern for each string

Pattern Matching

Group strings with identical patterns

Output

Return grouped strings as nested arrays

Key Takeaway

🎯 Key Insight: Strings that can be shifted into each other have identical character difference patterns

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is that strings in the same shifting sequence have identical difference patterns between adjacent characters. Best approach uses a hash map with pattern keys to group strings efficiently. Time: O(n×m), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Pattern Key	O(n × m)	O(n × m)	Create unique pattern signatures for each string based on character differences
Brute Force - Direct Comparison	O(n² × m)	O(n × m)	Compare each string with every other string by trying all possible shifts

Hash Map with Pattern Key — Algorithm Steps

Step 1: For each string, calculate differences between adjacent characters
Step 2: Create normalized pattern as key (handle wraparound a→z)
Step 3: Use hash map to group strings with identical patterns
Step 4: Return all groups as list of lists

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate patterns

"abc" → [1,1], "bcd" → [1,1], "acf" → [2,3]

Group by pattern

Same pattern = same group

Return groups

Convert hash map values to list

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_GROUPS 1000
#define MAX_PATTERN_LEN 100

typedef struct {
    char pattern[MAX_PATTERN_LEN];
    char** strings;
    int size;
    int capacity;
} Group;

void getPattern(const char* s, char* pattern) {
    int len = strlen(s);
    if (len <= 1) {
        strcpy(pattern, "");
        return;
    }
    
    pattern[0] = '\0';
    for (int i = 1; i < len; i++) {
        int diff = (s[i] - s[i-1] + 26) % 26;
        char diffStr[10];
        sprintf(diffStr, "%d", diff);
        if (i > 1) strcat(pattern, ",");
        strcat(pattern, diffStr);
    }
}

char*** solution(char** strings, int stringsSize, int* returnSize, int** returnColumnSizes) {
    Group groups[MAX_GROUPS];
    int groupCount = 0;
    
    for (int i = 0; i < stringsSize; i++) {
        char pattern[MAX_PATTERN_LEN];
        getPattern(strings[i], pattern);
        
        int foundGroup = -1;
        for (int j = 0; j < groupCount; j++) {
            if (strcmp(groups[j].pattern, pattern) == 0) {
                foundGroup = j;
                break;
            }
        }
        
        if (foundGroup == -1) {
            strcpy(groups[groupCount].pattern, pattern);
            groups[groupCount].strings = malloc(stringsSize * sizeof(char*));
            groups[groupCount].strings[0] = malloc((strlen(strings[i]) + 1) * sizeof(char));
            strcpy(groups[groupCount].strings[0], strings[i]);
            groups[groupCount].size = 1;
            groups[groupCount].capacity = stringsSize;
            groupCount++;
        } else {
            int idx = groups[foundGroup].size;
            groups[foundGroup].strings[idx] = malloc((strlen(strings[i]) + 1) * sizeof(char));
            strcpy(groups[foundGroup].strings[idx], strings[i]);
            groups[foundGroup].size++;
        }
    }
    
    char*** result = malloc(groupCount * sizeof(char**));
    *returnColumnSizes = malloc(groupCount * sizeof(int));
    for (int i = 0; i < groupCount; i++) {
        result[i] = groups[i].strings;
        (*returnColumnSizes)[i] = groups[i].size;
    }
    
    *returnSize = groupCount;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for array of strings
    char** strings = malloc(100 * sizeof(char*));
    int stringsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"')) end--;
        *(end + 1) = 0;
        
        strings[stringsSize] = malloc((strlen(token) + 1) * sizeof(char));
        strcpy(strings[stringsSize], token);
        stringsSize++;
        
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* returnColumnSizes;
    char*** result = solution(strings, stringsSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("\"%s\"", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Process each of n strings once, calculating m-1 differences per string

✓ Linear Growth

Space Complexity

O(n × m)

Hash map stores pattern keys and groups, total space for n strings of average length m

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Pattern Key — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler