Groups of Strings - Practice Coding Problems

Groups of Strings - Problem

You are given a 0-indexed array of strings words. Each string consists of lowercase English letters only. No letter occurs more than once in any string of words.

Two strings s1 and s2 are said to be connected if the set of letters of s2 can be obtained from the set of letters of s1 by any one of the following operations:

Adding exactly one letter to the set of the letters of s1.
Deleting exactly one letter from the set of the letters of s1.
Replacing exactly one letter from the set of the letters of s1 with any letter, including itself.

The array words can be divided into one or more non-intersecting groups. A string belongs to a group if any one of the following is true:

It is connected to at least one other string of the group.
It is the only string present in the group.

Note that the strings in words should be grouped in such a manner that a string belonging to a group cannot be connected to a string present in any other group. It can be proved that such an arrangement is always unique.

Return an array ans of size 2 where:

ans[0] is the maximum number of groups words can be divided into, and
ans[1] is the size of the largest group.

Input & Output

Example 1 — Basic Grouping

$ Input: words = ["a","b","ab","cde"]

› Output: [3,2]

💡 Note: Groups: {"a","ab"} (connected by adding 'b'), {"b"} (isolated), {"cde"} (isolated). Total 3 groups, largest size 2.

Example 2 — Single Large Group

$ Input: words = ["a","ab","abc"]

› Output: [1,3]

💡 Note: All strings are connected: "a" → "ab" (add 'b'), "ab" → "abc" (add 'c'). One group of size 3.

Example 3 — All Isolated

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

› Output: [3,1]

💡 Note: No connections possible (differ by more than one character). 3 groups, each of size 1.

Constraints

1 ≤ words.length ≤ 2 × 10⁴
1 ≤ words[i].length ≤ 26
words[i] consists of lowercase English letters only
No letter occurs more than once in any words[i]

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array of strings with unique characters

Connection Rules

Add/delete/replace one character operations

Group Formation

Connected components in the graph

Key Takeaway

🎯 Key Insight: Use graph connectivity to find components - strings that can transform into each other form groups

Asked in

G Google 15 f Meta 12 a Amazon 8 M Microsoft 6

The key insight is to model this as a graph connectivity problem where strings are connected if they differ by exactly one character operation. The optimal approach uses bit manipulation to represent character sets efficiently and Union-Find to group connected components. Time: O(n² × α(n)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Character Comparison	O(n² × L)	O(n²)	Compare every pair of strings character by character to build groups
Bit Manipulation with Union-Find	O(n² × α(n))	O(n)	Use bitmasks to represent character sets and Union-Find for efficient grouping

Brute Force with Character Comparison — Algorithm Steps

Step 1: For each pair of strings, check if they are connected by comparing character sets
Step 2: Build an adjacency graph of connected strings
Step 3: Use DFS to find all connected components (groups)
Step 4: Count total groups and find the largest group size

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Pairs

Check each string pair for connection

Build Graph

Create adjacency list of connections

Find Groups

Use DFS to find connected components

Code -

solution.c — C

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

#define MAX_WORDS 1000
#define MAX_LEN 100

bool areConnected(char* s1, char* s2) {
    bool set1[26] = {false};
    bool set2[26] = {false};
    
    for (int i = 0; s1[i]; i++) {
        set1[s1[i] - 'a'] = true;
    }
    for (int i = 0; s2[i]; i++) {
        set2[s2[i] - 'a'] = true;
    }
    
    int diff1 = 0, diff2 = 0;
    for (int i = 0; i < 26; i++) {
        if (set1[i] && !set2[i]) diff1++;
        if (set2[i] && !set1[i]) diff2++;
    }
    
    int len1 = strlen(s1), len2 = strlen(s2);
    
    if (len1 == len2) {
        return diff1 <= 1 && diff2 <= 1;
    }
    
    if (abs(len1 - len2) == 1) {
        return diff1 <= 1 && diff2 <= 1;
    }
    
    return false;
}

void dfs(int node, int graph[][MAX_WORDS], int graphSize[], bool visited[], int* component, int* compSize) {
    visited[node] = true;
    component[(*compSize)++] = node;
    
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (!visited[neighbor]) {
            dfs(neighbor, graph, graphSize, visited, component, compSize);
        }
    }
}

int* solution(char words[][MAX_LEN], int wordsSize) {
    int graph[MAX_WORDS][MAX_WORDS];
    int graphSize[MAX_WORDS] = {0};
    
    for (int i = 0; i < wordsSize; i++) {
        for (int j = i + 1; j < wordsSize; j++) {
            if (areConnected(words[i], words[j])) {
                graph[i][graphSize[i]++] = j;
                graph[j][graphSize[j]++] = i;
            }
        }
    }
    
    bool visited[MAX_WORDS] = {false};
    int groupSizes[MAX_WORDS];
    int groupCount = 0;
    
    for (int i = 0; i < wordsSize; i++) {
        if (!visited[i]) {
            int component[MAX_WORDS];
            int compSize = 0;
            dfs(i, graph, graphSize, visited, component, &compSize);
            groupSizes[groupCount++] = compSize;
        }
    }
    
    int maxSize = 0;
    for (int i = 0; i < groupCount; i++) {
        if (groupSizes[i] > maxSize) {
            maxSize = groupSizes[i];
        }
    }
    
    int* result = malloc(2 * sizeof(int));
    result[0] = groupCount;
    result[1] = maxSize;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char words[MAX_WORDS][MAX_LEN];
    int wordsSize = 0;
    
    char* token = strtok(line + 1, ",");
    while (token && wordsSize < MAX_WORDS) {
        int len = strlen(token);
        if (token[len-1] == ']') token[len-1] = '\0';
        
        int start = 0, end = strlen(token) - 1;
        while (token[start] == ' ' || token[start] == '"') start++;
        while (end >= 0 && (token[end] == ' ' || token[end] == '"' || token[end] == '\n')) end--;
        
        int idx = 0;
        for (int i = start; i <= end; i++) {
            words[wordsSize][idx++] = token[i];
        }
        words[wordsSize][idx] = '\0';
        wordsSize++;
        
        token = strtok(NULL, ",");
    }
    
    int* result = solution(words, wordsSize);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × L)

n² pairs to compare, L average string length for each comparison

⚠ Quadratic Growth

Space Complexity

O(n²)

Adjacency list can store up to n² connections

⚠ Quadratic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

234 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

Brute Force with Character Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler