#2068

Easy

LeetCode Problem Workspace

Check Whether Two Strings are Almost Equivalent

Solve Check Whether Two Strings are Almost Equivalent by counting letters and rejecting any character whose frequency gap exceeds three.

hash table string counting

Problem Statement

You are given two lowercase English strings, word1 and word2, with the same length. These strings are called almost equivalent when every letter from a to z appears with counts that differ by no more than 3 between the two words.

Return true when that rule holds for all 26 letters, otherwise return false. For example, word1 = "aaaa" and word2 = "bccb" should return false because the count of a differs by 4, which breaks the allowed limit.

Examples

Example 1

Input: word1 = "aaaa", word2 = "bccb"

Output: false

There are 4 'a's in "aaaa" but 0 'a's in "bccb". The difference is 4, which is more than the allowed 3.

Example 2

Input: word1 = "abcdeef", word2 = "abaaacc"

Output: true

The differences between the frequencies of each letter in word1 and word2 are at most 3:

'a' appears 1 time in word1 and 4 times in word2. The difference is 3.
'b' appears 1 time in word1 and 1 time in word2. The difference is 0.
'c' appears 1 time in word1 and 2 times in word2. The difference is 1.
'd' appears 1 time in word1 and 0 times in word2. The difference is 1.
'e' appears 2 times in word1 and 0 times in word2. The difference is 2.
'f' appears 1 time in word1 and 0 times in word2. The difference is 1.

Example 3

Input: word1 = "cccddabba", word2 = "babababab"

Output: true

The differences between the frequencies of each letter in word1 and word2 are at most 3:

'a' appears 2 times in word1 and 4 times in word2. The difference is 2.
'b' appears 2 times in word1 and 5 times in word2. The difference is 3.
'c' appears 3 times in word1 and 0 times in word2. The difference is 3.
'd' appears 2 times in word1 and 0 times in word2. The difference is 2.

Constraints

n == word1.length == word2.length
1 <= n <= 100
word1 and word2 consist only of lowercase English letters.

Solution Approach

Count both words by character

Use a frequency structure for lowercase letters, either two arrays of size 26 or one array that adds counts from word1 and subtracts counts from word2. This directly matches the Hash Table plus String pattern because the entire decision depends on letter counts, not character order.

Compare the frequency difference for each letter

After processing both strings, scan all 26 letters and check the absolute difference for each one. The problem does not ask whether the strings are close overall; it asks whether every single character stays within the threshold of 3.

Return early on the first violation

As soon as one letter has a gap greater than 3, return false. This prevents unnecessary work and reflects the main failure mode in this problem: one heavily overrepresented character, like a in "aaaa" versus zero a letters in the second string.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N) because you scan the two strings once and then inspect 26 letters. The space complexity is O(1) because the counting structure never grows beyond the fixed lowercase alphabet.

What Interviewers Usually Probe

They want counting, not sorting, because only per-letter frequency differences matter.
The fixed alphabet size hints that an array of 26 is cleaner than a general map.
An early return on any difference greater than 3 shows you understand the exact acceptance condition.

Common Pitfalls or Variants

Common pitfalls

Comparing total mismatches instead of checking each individual letter gap against 3.
Using sorting, which adds unnecessary work and hides the direct counting pattern of this problem.
Forgetting letters that appear in one word but not the other, which is exactly why "aaaa" versus "bccb" fails.

Follow-up variants

Change the threshold from 3 to k and keep the same counting scan.
Allow uppercase or arbitrary characters, which shifts the 26-slot array toward a hash map.
Ask for the maximum frequency gap instead of a boolean result, using the same counts but a different final check.

FAQ

What is the key idea in Check Whether Two Strings are Almost Equivalent?

Count each lowercase letter in both words and verify that every frequency difference is at most 3. The string order never matters in this problem.

Why is this tagged as Hash Table, String, and Counting?

You read characters from strings, store occurrence counts, and decide the answer from those counts. That is the full pattern here, even when implemented with an array instead of a hash map.

Can I use one array instead of two for this problem?

Yes. Add 1 for each character in word1 and subtract 1 for each character in word2, then check whether any absolute value is greater than 3.

Why is sorting not a good fit here?

Sorting changes the problem into an order-based comparison, but this task only cares about frequency gaps for each letter. Counting is simpler and keeps the intended O(N) time.

What causes the false result in the example word1 = "aaaa", word2 = "bccb"?

The letter a appears 4 times in word1 and 0 times in word2, so the difference is 4. Since 4 is greater than 3, the strings are not almost equivalent.

terminal

Solution

Solution 1: Counting

We can create an array $cnt$ of length $26$ to record the difference in the number of times each letter appears in the two strings. Then we traverse $cnt$, if any letter appears the difference in the number of times greater than $3$, then return `false`, otherwise return `true`.

1

2

3

4

5

6

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        cnt = Counter(word1)
        for c in word2:
            cnt[c] -= 1
        return all(abs(x) <= 3 for x in cnt.values())

Continue Practicing

#2053 kth distinct string in an array #2085 count common words with one occurrence #2023 number of pairs of strings with concatenation equal to target