Determine if Two Strings Are Close

medium string hash map

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.

Inputa = "aabbcc", b = "bbccaa"

Outputtrue

Letters {a, b, c} match; counts [2, 2, 2] match.

from collections import Counter
def close_strings(a, b):
    if len(a) != len(b): return False
    fa, fb = Counter(a), Counter(b)
    if set(fa) != set(fb): return False
    return sorted(fa.values()) == sorted(fb.values())

function closeStrings(a, b) {
  if (a.length !== b.length) return false;
  const fa = {}, fb = {};
  for (const c of a) fa[c] = (fa[c] || 0) + 1;
  for (const c of b) fb[c] = (fb[c] || 0) + 1;
  const ka = Object.keys(fa).sort().join("");
  const kb = Object.keys(fb).sort().join("");
  if (ka !== kb) return false;
  const va = Object.values(fa).sort((x, y) => x - y);
  const vb = Object.values(fb).sort((x, y) => x - y);
  return va.join(",") === vb.join(",");
}

class Solution {
    public boolean closeStrings(String a, String b) {
        if (a.length() != b.length()) return false;
        Map<Character, Integer> fa = new HashMap<>(), fb = new HashMap<>();
        for (char c : a.toCharArray()) fa.merge(c, 1, Integer::sum);
        for (char c : b.toCharArray()) fb.merge(c, 1, Integer::sum);
        if (!fa.keySet().equals(fb.keySet())) return false;
        List<Integer> va = new ArrayList<>(fa.values()); Collections.sort(va);
        List<Integer> vb = new ArrayList<>(fb.values()); Collections.sort(vb);
        return va.equals(vb);
    }
}

bool closeStrings(string a, string b) {
    if (a.size() != b.size()) return false;
    unordered_map<char, int> fa, fb;
    for (char c : a) fa[c]++;
    for (char c : b) fb[c]++;
    set<char> ka, kb;
    for (auto& p : fa) ka.insert(p.first);
    for (auto& p : fb) kb.insert(p.first);
    if (ka != kb) return false;
    vector<int> va, vb;
    for (auto& p : fa) va.push_back(p.second);
    for (auto& p : fb) vb.push_back(p.second);
    sort(va.begin(), va.end()); sort(vb.begin(), vb.end());
    return va == vb;
}

Explanation

The two allowed moves are sneaky, but they boil down to two simple facts. Swapping characters lets you reorder freely, and swapping all of one letter for another lets you relabel a frequency to another letter. So we never compare the actual arrangement; we only compare which letters exist and how often each one shows up.

That gives us two checks. First, both strings must use the exact same set of letters (operation 2 can rename a letter, but only to a letter that already exists). Second, the multiset of counts must match, because operation 2 only relabels counts, it never changes the list of count values.

In code we build a frequency map for each string with Counter. We compare set(fa) == set(fb) for the letter sets, then compare sorted(fa.values()) == sorted(fb.values()) for the counts. Sorting lets us match counts regardless of which letter owns them.

Example: a = "aabbcc", b = "bbccaa". Both use letters {a, b, c}, and both have sorted counts [2, 2, 2], so the answer is true. If b were "aabbc", the lengths differ, so we return false immediately.

The early length check saves work, and because we only count and sort a tiny alphabet, this runs fast no matter how long the strings are.

Time: O(n + α log α) (α = alphabet) Space: O(α)