Groups of Special-Equivalent Strings - Practice Coding Problems

Groups of Special-Equivalent Strings - Problem

You are given an array of strings words where all strings have the same length.

In one move, you can swap any two even indexed characters or any two odd indexed characters of a string words[i].

Two strings words[i] and words[j] are special-equivalent if after any number of moves, words[i] == words[j].

For example, words[i] = "zzxy" and words[j] = "xyzz" are special-equivalent because we may make the moves "zzxy" → "xzzy" → "xyzz".

A group of special-equivalent strings from words is a non-empty subset where:

Every pair of strings in the group are special-equivalent
The group is the largest size possible (no string outside the group is special-equivalent to every string in the group)

Return the number of groups of special-equivalent strings from words.

Input & Output

Example 1 — Basic Grouping

$ Input: words = ["abc","acb","bac","bca","cab","cba"]

› Output: 3

💡 Note: Group 1: ["abc","bac"] (even: "ac", odd: "b"), Group 2: ["acb","bca","cab","cba"] (even: "ac"/"bc"/"cb", odd: "cb"/"a"/"a"), Group 3: singles. After proper analysis: 3 distinct signatures.

Example 2 — All Same Group

$ Input: words = ["a"]

› Output: 1

💡 Note: Single string forms one group.

Example 3 — No Equivalents

$ Input: words = ["aa","bb","ab","ba"]

› Output: 4

💡 Note: "aa" (even:"a", odd:"a"), "bb" (even:"b", odd:"b"), "ab" (even:"a", odd:"b"), "ba" (even:"b", odd:"a") - all different signatures.

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 20
words[i] consists of lowercase English letters
All the strings are of the same length

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array of strings with same length

Character Separation

Split into even and odd positioned characters

Group Formation

Count unique signature patterns

Key Takeaway

🎯 Key Insight: Two strings belong to the same group if their sorted even-positioned and odd-positioned characters match

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that two strings are special-equivalent if their even-positioned and odd-positioned characters can be rearranged to match. Best approach is hash map with signatures - create a unique signature by sorting even and odd characters separately. Time: O(n × m log m), Space: O(n × m)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Signature	O(n × m log m)	O(n × m)	Create a unique signature for each string and group by signature
Brute Force Comparison	O(n² × m log m)	O(m)	Compare every pair of strings to check if they are special-equivalent

Hash Map with Signature — Algorithm Steps

For each string, extract even and odd characters
Sort both groups to create signature
Use hash map to count unique signatures
Return the number of unique signatures

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Signature

Sort even and odd characters separately

Hash Mapping

Store signatures in hash map

Count Groups

Number of unique signatures

Code -

solution.c — C

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

typedef struct {
    char signature[102];
} Signature;

int compare_char(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

int compare_signature(const void *a, const void *b) {
    return strcmp(((Signature*)a)->signature, ((Signature*)b)->signature);
}

int solution(char words[][51], int n) {
    Signature signatures[1000];
    int sigCount = 0;
    
    for (int i = 0; i < n; i++) {
        char evenChars[51], oddChars[51];
        int evenIdx = 0, oddIdx = 0;
        int len = strlen(words[i]);
        
        for (int j = 0; j < len; j++) {
            if (j % 2 == 0) {
                evenChars[evenIdx++] = words[i][j];
            } else {
                oddChars[oddIdx++] = words[i][j];
            }
        }
        
        evenChars[evenIdx] = '\0';
        oddChars[oddIdx] = '\0';
        
        qsort(evenChars, evenIdx, sizeof(char), compare_char);
        qsort(oddChars, oddIdx, sizeof(char), compare_char);
        
        sprintf(signatures[sigCount].signature, "%s|%s", evenChars, oddChars);
        sigCount++;
    }
    
    qsort(signatures, sigCount, sizeof(Signature), compare_signature);
    
    int uniqueCount = 1;
    for (int i = 1; i < sigCount; i++) {
        if (strcmp(signatures[i].signature, signatures[i-1].signature) != 0) {
            uniqueCount++;
        }
    }
    
    return uniqueCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char words[1000][51];
    int count = 0;
    
    char* ptr = strchr(line, '[') + 1;
    char* end = strrchr(line, ']');
    *end = '\0';
    
    char* token = strtok(ptr, ",");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        char* wordEnd = token + strlen(token) - 1;
        while (*wordEnd == ' ' || *wordEnd == '"') *wordEnd-- = '\0';
        strcpy(words[count++], token);
        token = strtok(NULL, ",");
    }
    
    int result = solution(words, count);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m log m)

Process n strings, each requires sorting m characters

⚡ Linearithmic

Space Complexity

O(n × m)

Hash map stores signature for each string

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 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 Signature — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler