Two Strings Are Close

medium string hash map

Problem

Two strings are close when one can be transformed into the other by either swapping any two characters' positions, or swapping every occurrence of one character with every occurrence of another. Equivalently: they share the same letter set, and the same multiset of letter counts.

Inputa = "aabbcc", b = "bbccaa"

Outputtrue

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

from collections import Counter
def are_close(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 areClose(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 areClose(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 areClose(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;
}

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