Determine if Two Strings Are Close

Medium
678.

Determine if Two Strings Are Close

Determine if Two Strings Are Close is a medium coding problem on strings, hash table and sorting, asked in Amazon, Google and Flipkart interviews.

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

  1. swap any two existing characters (for example "abcde" to "aecdb");
  2. 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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var closeStrings = function(word1, word2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Determine if Two Strings Are Close — Problem & Solution

Determine if Two Strings Are Close solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Determine if Two Strings Are Close is a medium coding problem on strings, hash table and sorting, asked in Amazon, Google and Flipkart interviews.

Problem statement

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

  1. swap any two existing characters (for example "abcde" to "aecdb");
  2. 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.

Hints for Determine if Two Strings Are Close

  1. Hint 1

    Operation 1 says order does not matter — only the frequencies do.

  2. Hint 2

    Operation 2 says the frequencies can be permuted among the characters, but no character can be created or destroyed.

  3. Hint 3

    So two conditions: the two strings use exactly the same set of letters, and their sorted frequency lists are identical.

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

  1. Count the letters of each word.
  2. Check that a letter is present in one word exactly when it is present in the other.
  3. 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)

Java

public static boolean closeStrings(String word1, String word2) {
    if (word1.length() != word2.length()) return false;
    int[] c1 = new int[26];
    int[] c2 = new int[26];
    for (int i = 0; i < word1.length(); i++) c1[word1.charAt(i) - 'a']++;
    for (int i = 0; i < word2.length(); i++) c2[word2.charAt(i) - 'a']++;
    for (int c = 0; c < 26; c++) {
        if ((c1[c] == 0) != (c2[c] == 0)) return false;
    }
    int[] a = c1.clone();
    int[] b = c2.clone();
    Arrays.sort(a);
    Arrays.sort(b);
    return Arrays.equals(a, b);
}

C++

bool closeStrings(string word1, string word2) {
    if (word1.size() != word2.size()) return false;
    vector<int> c1(26, 0), c2(26, 0);
    for (char c : word1) c1[c - 'a']++;
    for (char c : word2) c2[c - 'a']++;
    for (int c = 0; c < 26; c++) {
        if ((c1[c] == 0) != (c2[c] == 0)) return false;
    }
    vector<int> a = c1, b = c2;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a == b;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets