Similar String Groups - Practice Coding Problems

Input & Output

Example 1 — Basic Grouping

$ Input: strs = ["tars","rats","arts","star"]

› Output: 2

💡 Note: "tars" and "rats" are similar (swap positions 0,2). "rats" and "arts" are similar (swap positions 0,1). So {"tars","rats","arts"} form one group. "star" forms its own group. Total: 2 groups.

Example 2 — All Connected

$ Input: strs = ["abc","bac"]

› Output: 1

💡 Note: "abc" and "bac" are similar by swapping positions 0 and 1. Both strings form one group.

Example 3 — All Separate

$ Input: strs = ["abc","def","ghi"]

› Output: 3

💡 Note: None of the strings are similar to each other (would need more than 2 swaps). Each string forms its own group.

Constraints

1 ≤ strs.length ≤ 300
1 ≤ strs[i].length ≤ 300
strs[i] consists of lowercase letters only
All the strings of strs are the same length
All the strings of strs are anagrams of each other

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Array of anagram strings that may be similar

Find Similarities

Check which pairs can be made equal with ≤2 swaps

Group Connected

Count connected components of similar strings

Key Takeaway

🎯 Key Insight: Model similarity as graph edges and count connected components using Union-Find or DFS

Asked in

G Google 25 f Facebook 18 a Amazon 15

The key insight is to model this as a graph connectivity problem. Two strings are similar if they differ by at most 2 character positions. We need to find connected components where strings are transitively connected through similarity relationships. The Union-Find approach is most efficient with time complexity O(n² × m × α(n)) and space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Disjoint Set)	O(n² × m × α(n))	O(n)	Use Union-Find data structure to efficiently group similar strings
Brute Force with DFS	O(n² × m)	O(n²)	Check similarity between all pairs and use DFS to find connected components

Union-Find (Disjoint Set) — Algorithm Steps

Initialize Union-Find with n components
For each pair of similar strings, union them
Count number of distinct components

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Each string starts as its own component

Union Similar

Merge components when strings are similar

Count Roots

Count distinct root components

Code -

solution.c — C

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

typedef struct {
    int* parent;
    int* rank;
    int n;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)calloc(n, sizeof(int));
    uf->n = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionSets(UnionFind* uf, int x, int y) {
    int px = find(uf, x), py = find(uf, y);
    if (px == py) return;
    if (uf->rank[px] < uf->rank[py]) {
        int temp = px; px = py; py = temp;
    }
    uf->parent[py] = px;
    if (uf->rank[px] == uf->rank[py]) {
        uf->rank[px]++;
    }
}

bool isSimilar(const char* s1, const char* s2) {
    if (strcmp(s1, s2) == 0) return true;
    int diffCount = 0;
    int len = strlen(s1);
    for (int i = 0; i < len; i++) {
        if (s1[i] != s2[i]) {
            diffCount++;
            if (diffCount > 2) return false;
        }
    }
    return diffCount == 2;
}

int solution(char** strs, int n) {
    if (n <= 1) return n;
    
    UnionFind* uf = createUnionFind(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isSimilar(strs[i], strs[j])) {
                unionSets(uf, i, j);
            }
        }
    }
    
    // Count unique components
    bool* seen = (bool*)calloc(n, sizeof(bool));
    int components = 0;
    
    for (int i = 0; i < n; i++) {
        int root = find(uf, i);
        if (!seen[root]) {
            seen[root] = true;
            components++;
        }
    }
    
    free(uf->parent);
    free(uf->rank);
    free(uf);
    free(seen);
    
    return components;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char** strs = (char**)malloc(100 * sizeof(char*));
    int n = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && n < 100) {
            while (*token == ' ' || *token == '"') token++;
            char* end = token + strlen(token) - 1;
            while (end > token && (*end == ' ' || *end == '"' || *end == '\n')) {
                *end = '\0';
                end--;
            }
            
            strs[n] = (char*)malloc((strlen(token) + 1) * sizeof(char));
            strcpy(strs[n], token);
            n++;
            
            token = strtok(NULL, ",]");
        }
    }
    
    printf("%d\n", solution(strs, n));
    
    for (int i = 0; i < n; i++) {
        free(strs[i]);
    }
    free(strs);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m × α(n))

n² pairs to check, each similarity check O(m), union operations O(α(n)) with inverse Ackermann

⚠ Quadratic Growth

Space Complexity

O(n)

Union-Find parent and rank arrays of size n

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 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

Union-Find (Disjoint Set) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler