Count Pairs Of Similar Strings - Practice Coding Problems

Count Pairs Of Similar Strings - Problem

You are given a 0-indexed string array words.

Two strings are similar if they consist of the same characters.

For example, "abca" and "cba" are similar since both consist of characters 'a', 'b', and 'c'.
However, "abacba" and "bcfd" are not similar since they do not consist of the same characters.

Return the number of pairs (i, j) such that 0 <= i < j < words.length and the two strings words[i] and words[j] are similar.

Input & Output

Example 1 — Basic Case

$ Input: words = ["aba","aab","abc","cba"]

› Output: 2

💡 Note: Pairs (0,1) and (2,3) are similar: "aba" and "aab" both have characters {a,b}, while "abc" and "cba" both have characters {a,b,c}

Example 2 — All Different

$ Input: words = ["aab","ab","aa"]

› Output: 1

💡 Note: Only pair (0,1) is similar: "aab" and "ab" both have characters {a,b}, while "aa" only has character {a}

Example 3 — All Same

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

› Output: 3

💡 Note: All strings have the same character set {a,b,c}, so all 3 pairs (0,1), (0,2), and (1,2) are similar

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 100
words[i] consists of only lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings with different character combinations

Process

Group strings by their unique character sets

Output

Count total pairs within all groups

Key Takeaway

🎯 Key Insight: Similar strings have identical character sets - use bit masks or string signatures to group efficiently

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is that two strings are similar if they contain the exact same set of unique characters, regardless of frequency or order. The most efficient approach uses bit manipulation to represent character sets as integers, enabling O(1) comparisons and efficient grouping. Time: O(n × m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Mask Optimization	O(n × m)	O(n)	Use bit masks to represent character sets for faster comparison and grouping
Character Signature Grouping	O(n × m)	O(n × k)	Group strings by their character signatures and count pairs within groups
Brute Force Comparison	O(n² × m)	O(m)	Compare each pair of strings by converting to character sets

Bit Mask Optimization — Algorithm Steps

Convert each string to a bit mask representing its character set
Group strings by identical bit masks using hash map
Count pairs within each group using combinatorial formula

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Bit Masks

Convert each string to binary representation of character set

Group by Mask

Group strings with identical bit patterns

Count Combinations

Calculate pairs using combinatorial math

Code -

solution.c — C

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

typedef struct {
    int mask;
    int count;
} Group;

int solution(char words[][101], int n) {
    Group groups[1000]; // Assuming max 1000 different masks
    int groupCount = 0;
    
    for (int i = 0; i < n; i++) {
        // Create bit mask for characters
        int mask = 0;
        for (int j = 0; words[i][j]; j++) {
            mask |= (1 << (words[i][j] - 'a'));
        }
        
        // Find or create group
        int found = -1;
        for (int j = 0; j < groupCount; j++) {
            if (groups[j].mask == mask) {
                found = j;
                break;
            }
        }
        
        if (found >= 0) {
            groups[found].count++;
        } else {
            groups[groupCount].mask = mask;
            groups[groupCount].count = 1;
            groupCount++;
        }
    }
    
    // Count pairs within each group
    int count = 0;
    for (int i = 0; i < groupCount; i++) {
        int groupSize = groups[i].count;
        count += groupSize * (groupSize - 1) / 2;
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for JSON array
    char words[1000][101];
    int n = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) ptr++;
    
    char* token = strtok(ptr, ",]");
    while (token && n < 1000) {
        // Remove quotes and whitespace
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"')) end--;
        *(end + 1) = 0;
        
        strcpy(words[n], token);
        n++;
        token = strtok(NULL, ",]");
    }
    
    int result = solution(words, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Process n strings, each taking O(m) time to create bit mask where m is string length

✓ Linear Growth

Space Complexity

O(n)

Hash map stores at most n different bit masks (integers)

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

450 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

Bit Mask Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler