Determine if Two Strings Are Close — Medium Problem & Solution

Two strings are close if one can be turned into the other using these operations any number of times: swap any two existing characters (for example "abcde"…

Difficulty: Medium
Topics: Strings, Hash Table, Sorting, Counting
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two strings are close if one can be turned into the other using these operations any number of times:

swap any two existing characters (for example "abcde" to "aecdb");
transform every occurrence of one existing character into another existing character, and vice versa (for example "aacabb" to "bbcbaa" by swapping all a's with all b's).

Return true if word1 and word2 are close.

Example 1

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: Swapping characters is enough.

Example 2

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: Neither operation changes the length.

Example 3

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: Both use {a,b,c} and both have the frequency multiset {1,2,3}.

Constraints

1 <= word1.length, word2.length <= 100000
Both strings consist of lowercase English letters.

How to solve Determine if Two Strings Are Close

Swaps make order irrelevant; the second operation lets frequencies move between letters but never introduces a new letter. That leaves exactly two invariants to compare.

Approach

Count the letters of each word.
Check that a letter is present in one word exactly when it is present in the other.
Collect the non-zero counts from each word, sort both lists, and check they match.

Why it works

The first operation preserves the multiset of counts and the set of letters used; the second permutes counts among used letters, again preserving both. Conversely, when both invariants match, a sequence of the second operation can align the counts letter by letter and swaps finish the job — so the two conditions are exactly right.

Complexity

Time — O(n + 26 log 26)
Space — O(1)

Pitfalls

Comparing only the sorted frequency lists accepts "aaabb" and "cccdd", which use different letters.
Comparing only the letter sets accepts "aaab" and "aabb", whose frequency multisets {1,3} and {2,2} differ.
Different lengths can be rejected immediately.

Reference solution

Python

def closeStrings(word1: str, word2: str) -> bool:
    if len(word1) != len(word2):
        return False
    c1 = [0] * 26
    c2 = [0] * 26
    for ch in word1:
        c1[ord(ch) - 97] += 1
    for ch in word2:
        c2[ord(ch) - 97] += 1
    for i in range(26):
        if (c1[i] == 0) != (c2[i] == 0):
            return False
    return sorted(x for x in c1 if x) == sorted(x for x in c2 if x)

JavaScript

var closeStrings = function(word1, word2) {
    if (word1.length !== word2.length) return false;
    var c1 = [], c2 = [];
    for (var t = 0; t < 26; t++) { c1.push(0); c2.push(0); }
    for (var i = 0; i < word1.length; i++) c1[word1.charCodeAt(i) - 97]++;
    for (var j = 0; j < word2.length; j++) c2[word2.charCodeAt(j) - 97]++;
    for (var c = 0; c < 26; c++) {
        if ((c1[c] === 0) !== (c2[c] === 0)) return false;
    }
    var f1 = [], f2 = [];
    for (var k = 0; k < 26; k++) {
        if (c1[k] > 0) f1.push(c1[k]);
        if (c2[k] > 0) f2.push(c2[k]);
    }
    f1.sort(function(a, b) { return a - b; });
    f2.sort(function(a, b) { return a - b; });
    if (f1.length !== f2.length) return false;
    for (var m = 0; m < f1.length; m++) {
        if (f1[m] !== f2[m]) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue