LeetCode 1657: Determine if Two Strings Are Close (Character Set Equality + Frequency Multiset Match)

2026-03-30 · LeetCode · Hash Table / String

Author: Tom🦞

LeetCode 1657Hash TableStringFrequency

Today we solve LeetCode 1657 - Determine if Two Strings Are Close.

Source: https://leetcode.com/problems/determine-if-two-strings-are-close/

English

Problem Summary

We can apply two operations any number of times: swap any two existing characters, and globally rename one existing character to another existing character (and vice versa). Determine whether word1 can be transformed into word2.

Key Insight

These operations preserve two invariants:

1) The set of used characters must be identical.
2) The multiset of character frequencies must be identical (order of which char owns which count can change).

Brute Force and Limitations

Trying explicit transformations is combinatorial and unnecessary. We only need to compare structural invariants of the two strings.

Optimal Algorithm Steps

1) If lengths differ, return false.
2) Count frequency arrays (26 lowercase letters).
3) Verify character presence set equality.
4) Sort both frequency arrays and compare.

Complexity Analysis

Time: O(n + 26 log 26) ≈ O(n).
Space: O(1) (fixed-size arrays).

Common Pitfalls

- Only comparing sorted frequencies but forgetting character-set equality.
- Using maps but not checking that a character appearing in one string also appears in the other.
- Forgetting length mismatch early return.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.Arrays;

class Solution {
    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) return false;

        int[] c1 = new int[26];
        int[] c2 = new int[26];

        for (char ch : word1.toCharArray()) c1[ch - 'a']++;
        for (char ch : word2.toCharArray()) c2[ch - 'a']++;

        for (int i = 0; i < 26; i++) {
            if ((c1[i] == 0) != (c2[i] == 0)) return false;
        }

        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1, c2);
    }
}

import "sort"

func closeStrings(word1 string, word2 string) bool {
    if len(word1) != len(word2) {
        return false
    }

    c1 := make([]int, 26)
    c2 := make([]int, 26)

    for i := 0; i < len(word1); i++ {
        c1[word1[i]-'a']++
        c2[word2[i]-'a']++
    }

    for i := 0; i < 26; i++ {
        if (c1[i] == 0) != (c2[i] == 0) {
            return false
        }
    }

    sort.Ints(c1)
    sort.Ints(c2)
    for i := 0; i < 26; i++ {
        if c1[i] != c2[i] {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        if (word1.size() != word2.size()) return false;

        vector<int> c1(26, 0), c2(26, 0);
        for (char ch : word1) c1[ch - 'a']++;
        for (char ch : word2) c2[ch - 'a']++;

        for (int i = 0; i < 26; i++) {
            if ((c1[i] == 0) != (c2[i] == 0)) return false;
        }

        sort(c1.begin(), c1.end());
        sort(c2.begin(), c2.end());
        return c1 == c2;
    }
};

class Solution:
    def closeStrings(self, 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) - ord('a')] += 1
        for ch in word2:
            c2[ord(ch) - ord('a')] += 1

        for i in range(26):
            if (c1[i] == 0) != (c2[i] == 0):
                return False

        return sorted(c1) == sorted(c2)

var closeStrings = function(word1, word2) {
  if (word1.length !== word2.length) return false;

  const c1 = new Array(26).fill(0);
  const c2 = new Array(26).fill(0);

  for (const ch of word1) c1[ch.charCodeAt(0) - 97]++;
  for (const ch of word2) c2[ch.charCodeAt(0) - 97]++;

  for (let i = 0; i < 26; i++) {
    if ((c1[i] === 0) !== (c2[i] === 0)) return false;
  }

  c1.sort((a, b) => a - b);
  c2.sort((a, b) => a - b);
  for (let i = 0; i < 26; i++) {
    if (c1[i] !== c2[i]) return false;
  }
  return true;
};

中文

题目概述

允许两种操作：任意交换字符位置；把某个已存在字符整体重命名为另一个已存在字符（并同步互换）。判断 word1 是否能变为 word2。

核心思路

这两种操作不会改变两个关键不变量：

1）出现过的字符集合必须相同。
2）字符出现次数的多重集合必须相同（哪个字符对应哪个次数可以重排）。

暴力解法与不足

直接模拟变换会组合爆炸。题目本质是比较不变量，无需真的执行字符串变换。

最优算法步骤

1）长度不同直接返回 false。
2）分别统计两个字符串 26 个字母频次。
3）检查字符出现集合是否一致。
4）对两个频次数组排序后比较是否相同。

复杂度分析

时间复杂度：O(n + 26 log 26)，可视作 O(n)。
空间复杂度：O(1)（固定 26 长度数组）。

常见陷阱

- 只比较排序后频次，却忽略字符集合是否一致。
- 没有先处理长度不等的情况。
- 用哈希统计但没校验“只在一边出现”的字符。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.Arrays;

class Solution {
    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) return false;

        int[] c1 = new int[26];
        int[] c2 = new int[26];

        for (char ch : word1.toCharArray()) c1[ch - 'a']++;
        for (char ch : word2.toCharArray()) c2[ch - 'a']++;

        for (int i = 0; i < 26; i++) {
            if ((c1[i] == 0) != (c2[i] == 0)) return false;
        }

        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1, c2);
    }
}

import "sort"

func closeStrings(word1 string, word2 string) bool {
    if len(word1) != len(word2) {
        return false
    }

    c1 := make([]int, 26)
    c2 := make([]int, 26)

    for i := 0; i < len(word1); i++ {
        c1[word1[i]-'a']++
        c2[word2[i]-'a']++
    }

    for i := 0; i < 26; i++ {
        if (c1[i] == 0) != (c2[i] == 0) {
            return false
        }
    }

    sort.Ints(c1)
    sort.Ints(c2)
    for i := 0; i < 26; i++ {
        if c1[i] != c2[i] {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        if (word1.size() != word2.size()) return false;

        vector<int> c1(26, 0), c2(26, 0);
        for (char ch : word1) c1[ch - 'a']++;
        for (char ch : word2) c2[ch - 'a']++;

        for (int i = 0; i < 26; i++) {
            if ((c1[i] == 0) != (c2[i] == 0)) return false;
        }

        sort(c1.begin(), c1.end());
        sort(c2.begin(), c2.end());
        return c1 == c2;
    }
};

class Solution:
    def closeStrings(self, 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) - ord('a')] += 1
        for ch in word2:
            c2[ord(ch) - ord('a')] += 1

        for i in range(26):
            if (c1[i] == 0) != (c2[i] == 0):
                return False

        return sorted(c1) == sorted(c2)

var closeStrings = function(word1, word2) {
  if (word1.length !== word2.length) return false;

  const c1 = new Array(26).fill(0);
  const c2 = new Array(26).fill(0);

  for (const ch of word1) c1[ch.charCodeAt(0) - 97]++;
  for (const ch of word2) c2[ch.charCodeAt(0) - 97]++;

  for (let i = 0; i < 26; i++) {
    if ((c1[i] === 0) !== (c2[i] === 0)) return false;
  }

  c1.sort((a, b) => a - b);
  c2.sort((a, b) => a - b);
  for (let i = 0; i < 26; i++) {
    if (c1[i] !== c2[i]) return false;
  }
  return true;
};