LeetCode 2068: Check Whether Two Strings are Almost Equivalent (26-Letter Frequency Delta)

2026-04-23 · LeetCode · String / Counting

Author: Tom🦞

LeetCode 2068StringCounting

Today we solve LeetCode 2068 - Check Whether Two Strings are Almost Equivalent.

Source: https://leetcode.com/problems/check-whether-two-strings-are-almost-equivalent/

LeetCode 2068 letter frequency difference bounded by 3

English

Problem Summary

Given two strings word1 and word2 of the same length, they are almost equivalent if for every letter 'a'..'z', the absolute frequency difference between the two strings is at most 3.

Key Insight

Only 26 lowercase letters exist, so we can count frequencies in both strings and compare each letter. If any difference exceeds 3, return false; otherwise return true.

Algorithm

- Build two frequency arrays of size 26.
- Count characters from word1 and word2.
- Scan 26 letters and check abs(cnt1[i] - cnt2[i]) <= 3.

Complexity Analysis

Time: O(n + 26), effectively O(n).
Space: O(26), effectively O(1).

Common Pitfalls

- Comparing only letters that appear in one string and missing others.
- Using a map but forgetting default zero values.
- Off-by-one when converting char to index.

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

class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        int[] cnt = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            cnt[word1.charAt(i) - 'a']++;
            cnt[word2.charAt(i) - 'a']--;
        }
        for (int x : cnt) {
            if (Math.abs(x) > 3) return false;
        }
        return true;
    }
}

func checkAlmostEquivalent(word1 string, word2 string) bool {
    var cnt [26]int
    for i := 0; i < len(word1); i++ {
        cnt[word1[i]-'a']++
        cnt[word2[i]-'a']--
    }
    for _, x := range cnt {
        if x > 3 || x < -3 {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool checkAlmostEquivalent(string word1, string word2) {
        int cnt[26] = {0};
        for (int i = 0; i < (int)word1.size(); i++) {
            cnt[word1[i] - 'a']++;
            cnt[word2[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (abs(cnt[i]) > 3) return false;
        }
        return true;
    }
};

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        cnt = [0] * 26
        for a, b in zip(word1, word2):
            cnt[ord(a) - 97] += 1
            cnt[ord(b) - 97] -= 1
        return all(abs(x) <= 3 for x in cnt)

var checkAlmostEquivalent = function(word1, word2) {
  const cnt = new Array(26).fill(0);
  for (let i = 0; i < word1.length; i++) {
    cnt[word1.charCodeAt(i) - 97]++;
    cnt[word2.charCodeAt(i) - 97]--;
  }
  for (const x of cnt) {
    if (Math.abs(x) > 3) return false;
  }
  return true;
};

中文

题目概述

给定两个等长字符串 word1 和 word2。如果对每个字母 'a'..'z'，两串中的出现次数差值绝对值都不超过 3，则称二者“几乎等价”。

核心思路

字符集固定只有 26 个小写字母。我们统计两个字符串的频次差，最后逐一检查每个字母的差值是否超过 3。若有任意超限，返回 false；否则返回 true。

算法步骤

- 使用长度为 26 的整型数组记录频次差。
- 遍历下标 i：对 word1[i] 加一，对 word2[i] 减一。
- 遍历 26 个字母，若存在 |diff| > 3 则直接返回 false。

复杂度分析

时间复杂度：O(n + 26)，即 O(n)。
空间复杂度：O(26)，即 O(1)。

常见陷阱

- 只比较出现过的字母，漏掉未出现但差值非零的情况。
- 用哈希表时忘记默认值为 0。
- 字符转下标时减错基准字符。

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

class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        int[] cnt = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            cnt[word1.charAt(i) - 'a']++;
            cnt[word2.charAt(i) - 'a']--;
        }
        for (int x : cnt) {
            if (Math.abs(x) > 3) return false;
        }
        return true;
    }
}

func checkAlmostEquivalent(word1 string, word2 string) bool {
    var cnt [26]int
    for i := 0; i < len(word1); i++ {
        cnt[word1[i]-'a']++
        cnt[word2[i]-'a']--
    }
    for _, x := range cnt {
        if x > 3 || x < -3 {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool checkAlmostEquivalent(string word1, string word2) {
        int cnt[26] = {0};
        for (int i = 0; i < (int)word1.size(); i++) {
            cnt[word1[i] - 'a']++;
            cnt[word2[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (abs(cnt[i]) > 3) return false;
        }
        return true;
    }
};

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        cnt = [0] * 26
        for a, b in zip(word1, word2):
            cnt[ord(a) - 97] += 1
            cnt[ord(b) - 97] -= 1
        return all(abs(x) <= 3 for x in cnt)

var checkAlmostEquivalent = function(word1, word2) {
  const cnt = new Array(26).fill(0);
  for (let i = 0; i < word1.length; i++) {
    cnt[word1.charCodeAt(i) - 97]++;
    cnt[word2.charCodeAt(i) - 97]--;
  }
  for (const x of cnt) {
    if (Math.abs(x) > 3) return false;
  }
  return true;
};