Check Whether Two Strings are Almost Equivalent - Solution & Explanation
Problem Statement
Two strings word1 and word2 are considered almost equivalent if the differences between the frequencies of each letter from 'a' to 'z' between word1 and word2 is at most 3.
Given two strings word1 and word2, each of length n, return true if word1 and word2 are almost equivalent, or false otherwise.
The frequency of a letter x is the number of times it occurs in the string.
Example 1:
Input: word1 = "aaaa", word2 = "bccb" Output: false Explanation: 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 Explanation: 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 Explanation: 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.length1 <= n <= 100word1andword2consist only of lowercase English letters.
Approach Overview
Problem Overview: You receive two equal-length strings word1 and word2. The task is to check whether the difference in frequency of every lowercase letter between the two strings is at most 3. If any character appears more than 3 times more in one string than the other, the strings are not almost equivalent.
The key observation: the exact positions of characters do not matter. Only the frequency of each letter matters. That immediately points toward a hash table or frequency counting solution.
Approach 1: Frequency Counting with Arrays (O(n) time, O(1) space)
Use two fixed-size arrays of length 26 to store counts of each lowercase letter. Iterate through both strings once and increment the appropriate index (c - 'a') for each character. After building the frequency arrays, iterate from 0..25 and compute the absolute difference for each letter. If any difference exceeds 3, return false. Otherwise the strings are almost equivalent.
This works because the alphabet size is constant. The comparison step always checks 26 entries regardless of input length, so the space remains constant. This approach is usually the fastest in practice and avoids hashing overhead.
Approach 2: Using HashMaps (O(n) time, O(k) space)
Store character frequencies using a HashMap for each string. Traverse word1 and word2, updating counts for each character. Then iterate through all lowercase letters or the union of keys in both maps. Compute the absolute difference between the counts from the two maps. If any difference is greater than 3, return false.
This approach is more flexible when the character set is not limited to lowercase letters. Hash maps automatically expand for any character set, making the solution adaptable beyond the typical string problems restricted to 26 letters. The tradeoff is slightly higher constant overhead compared to arrays.
Both methods rely on the same idea: compare per-character frequency differences using a simple counting technique. The difference threshold (3) becomes a straightforward validation step after computing counts.
Recommended for interviews: The array-based frequency counting approach. Interviewers expect candidates to recognize that lowercase letters allow a fixed-size counting array. It runs in O(n) time and O(1) space and demonstrates strong understanding of character frequency techniques. Mentioning the HashMap variant shows awareness of how the solution generalizes when the alphabet size is not fixed.
Approach 1: Frequency Counting with Arrays
This approach utilizes arrays to count the frequency of each letter from 'a' to 'z' for both strings. By iterating through the characters of each word, we can populate two frequency arrays. Then, by comparing the absolute differences between corresponding elements of these arrays, we can determine if the words are almost equivalent.
The function areAlmostEquivalent initializes two integer arrays of size 26 to zero, representing the frequencies of each character. It iterates through the characters of the input strings to populate these frequency arrays. Finally, it checks that the absolute difference for any character's frequency does not exceed 3, returning false if it does, and true otherwise.
Complexity
Time Complexity: O(n + 26), which simplifies to O(n) where n is the length of the words.
Space Complexity: O(1) since the frequency arrays have a constant size of 26.
Approach 2: Using HashMaps
This alternate approach uses the hashmap or hash table data structure to record character frequencies for both strings. Hash maps are dynamic, allowing insertion without specifying a fixed field size. The hash maps' keys are characters, and their values are frequencies. The function calculates differences between frequency keys of two maps.
The C++ code uses unordered_map containers to store character frequencies. The frequency difference analysis is done by iterating through alphabetical characters, ensuring deviations do not surpass 3.
Code
C++
Java
Python
JavaScript
Complexity
Time Complexity: O(n), limited by character frequency computation.
Space Complexity: O(1), determined by number of distinct characters, since max 26 distinct alphabets.
Approach 3: 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.
The time complexity is O(n) and the space complexity is O(C). Where n is the length of the string, and C is the size of the character set, and in this question C = 26.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Frequency Counting with Arrays | Time Complexity: O(n + 26), which simplifies to O(n) where n is the length of the words. |
| Using HashMaps | Time Complexity: O(n), limited by character frequency computation. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Counting with Arrays | O(n) | O(1) | Best when the character set is fixed (lowercase letters). Fastest and most memory-efficient. |
| Using HashMaps | O(n) | O(k) | Useful when characters are not limited to 26 letters or when handling arbitrary Unicode strings. |
Video Solution
Check whether two Strings are almost equivalent| LeetCode problem 2068 • Technosage • 7,295 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check Whether Two Strings are Almost Equivalent easy or hard?
Check Whether Two Strings are Almost Equivalent Python/Java solution
How to solve Check Whether Two Strings are Almost Equivalent in O(n)?
What is the best approach for Check Whether Two Strings are Almost Equivalent?
Is Check Whether Two Strings are Almost Equivalent asked at Google/Amazon/Meta?
What data structure is used in Check Whether Two Strings are Almost Equivalent?
What is the time complexity of Check Whether Two Strings are Almost Equivalent?
Ready to solve this problem?
Practice Check Whether Two Strings are Almost Equivalent with our built-in code editor and test cases.
Practice on FleetCode