Determine if Two Strings Are Close - Practice Coding Problems

Determine if Two Strings Are Close - Problem

Two strings are considered close if you can attain one from the other using the following operations:

Operation 1: Swap any two existing characters.

For example, abcde → aecdb

Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.

For example, aacabb → bbcbaa (all a's turn into b's, and all b's turn into a's)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Input & Output

Example 1 — Basic Character Swap

$ Input: word1 = "abc", word2 = "bca"

› Output: true

💡 Note: Both strings have same characters {a,b,c} and same frequency distribution [1,1,1]. We can transform abc → bca using swaps and character transformations.

Example 2 — Different Characters

$ Input: word1 = "a", word2 = "aa"

› Output: false

💡 Note: Different lengths and word2 has frequency [2] while word1 has frequency [1]. Cannot make them close.

Example 3 — Character Transformation

$ Input: word1 = "cabbba", word2 = "abbccc"

› Output: true

💡 Note: Both have characters {a,b,c}. word1 frequencies: a=1,b=4,c=1 → [1,1,4]. word2 frequencies: a=1,b=2,c=4 → [1,2,4]. Same sorted pattern [1,1,4] vs [1,2,4] - different, so false. Wait, let me recalculate... word1 has a=1,b=4,c=1, word2 has a=1,b=2,c=4. These have same characters but different frequency distributions, so actually false.

Constraints

1 ≤ word1.length, word2.length ≤ 10⁵
word1 and word2 contain only lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings with potentially different character arrangements

Check Closeness

Verify same character sets and frequency patterns

Result

True if strings are close, false otherwise

Key Takeaway

🎯 Key Insight: Strings are close if they have identical character sets and matching frequency distributions

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that two strings are close if they have the same set of characters and the same frequency distribution pattern. Best approach uses frequency counting arrays for O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Character Set + Frequency Check	O(n)	O(1)	Efficient single-pass solution using character arrays for O(n) time complexity
Brute Force - Try All Operations	O(n! × 26²)	O(n! × n)	Generate all possible strings from word1 using operations and check if word2 exists
Frequency Count Analysis	O(n log n)	O(1)	Count character frequencies and check if they can be rearranged to match

Optimized Character Set + Frequency Check — Algorithm Steps

Count frequencies using arrays (26 letters)
Check if character sets match
Count frequency patterns and compare

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Characters

Use arrays for O(1) counting of 26 letters

Pattern Analysis

Create frequency-of-frequencies pattern

Direct Compare

Compare patterns without sorting

Code -

solution.c — C

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

bool solution(char* word1, char* word2) {
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    
    if (len1 != len2) {
        return false;
    }
    
    // Count character frequencies
    int count1[26] = {0};
    int count2[26] = {0};
    
    for (int i = 0; i < len1; i++) {
        count1[word1[i] - 'a']++;
        count2[word2[i] - 'a']++;
    }
    
    // Check if both strings have same set of characters
    for (int i = 0; i < 26; i++) {
        if ((count1[i] == 0) != (count2[i] == 0)) {
            return false;
        }
    }
    
    // Count frequency patterns
    int freqPattern1[len1 + 1];
    int freqPattern2[len2 + 1];
    memset(freqPattern1, 0, sizeof(freqPattern1));
    memset(freqPattern2, 0, sizeof(freqPattern2));
    
    for (int i = 0; i < 26; i++) {
        if (count1[i] > 0) {
            freqPattern1[count1[i]]++;
        }
        if (count2[i] > 0) {
            freqPattern2[count2[i]]++;
        }
    }
    
    // Compare frequency patterns
    for (int i = 0; i <= len1; i++) {
        if (freqPattern1[i] != freqPattern2[i]) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char word1[1001], word2[1001];
    
    fgets(word1, sizeof(word1), stdin);
    word1[strcspn(word1, "\n")] = 0;
    
    fgets(word2, sizeof(word2), stdin);
    word2[strcspn(word2, "\n")] = 0;
    
    bool result = solution(word1, word2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies, then O(26) to compare patterns

✓ Linear Growth

Space Complexity

O(1)

Fixed arrays of size 26 for character counts and frequency patterns

✓ Linear Space

85.4K Views

Medium Frequency

~15 min Avg. Time

2.2K 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

Optimized Character Set + Frequency Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler