Check Whether Two Strings are Almost Equivalent — Solution
Check Whether Two Strings are Almost Equivalent solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check Whether Two Strings are Almost Equivalent is an easy coding problem on strings, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two strings are almost equivalent when, for every letter from 'a' to 'z', the number of times it occurs in one string differs from the number of times it occurs in the other by at most 3.
Given two lowercase strings word1 and word2 of the same length, return true if they are almost equivalent and false otherwise.
Example 1
Input: word1 = "duel", word2 = "lead"
Output: true
Example 2
Input: word1 = "kkkkkiro", word2 = "kairoabc"
Output: false
Explanation: `k` occurs 5 times in `word1` but once in `word2` — a gap of 4.
Example 3
Input: word1 = "aaab", word2 = "bbbb"
Output: true
Explanation: `a` differs by 3 and `b` by 3, which is allowed.
Constraints
n == word1.length == word2.length1 <= n <= 100word1 and word2 consist only of lowercase English letters
Hints for Check Whether Two Strings are Almost Equivalent
Hint 1
Only letter counts matter, not positions.
Hint 2
Count the 26 letters of each word (or add for
word1and subtract forword2in one array).Hint 3
Check that every one of the 26 differences has absolute value at most 3.
How to solve Check Whether Two Strings are Almost Equivalent
Keep one array of 26 signed counters: add 1 for each letter of word1, subtract 1 for each letter of word2. Each counter is then the frequency difference of its letter.
Approach
- Initialise
diff[26] = 0. - For each character of
word1, increment its counter; for each character ofword2, decrement it. - Return
trueexactly when every|diff[c]| <= 3.
Why it works
After both passes diff[c] = count1(c) - count2(c), which is precisely the quantity the definition bounds, and the check covers all 26 letters — including those absent from one or both words.
Complexity
- Time —
O(n + 26) - Space —
O(1)
Pitfalls
- Letters that appear in only one word must still be checked — iterate over all 26, not just one word's letters.
- The bound is inclusive: a difference of exactly 3 is fine.
- Use the absolute value; the gap may go either way.
Reference solution
Python
from collections import Counter
def checkAlmostEquivalent(word1: str, word2: str) -> bool:
c1, c2 = Counter(word1), Counter(word2)
return all(abs(c1[ch] - c2[ch]) <= 3 for ch in 'abcdefghijklmnopqrstuvwxyz')Java
public static boolean checkAlmostEquivalent(String word1, String word2) {
int[] diff = new int[26];
for (int i = 0; i < word1.length(); i++) diff[word1.charAt(i) - 'a']++;
for (int i = 0; i < word2.length(); i++) diff[word2.charAt(i) - 'a']--;
for (int d : diff) if (Math.abs(d) > 3) return false;
return true;
}C++
bool checkAlmostEquivalent(string word1, string word2) {
int diff[26] = {0};
for (char c : word1) diff[c - 'a']++;
for (char c : word2) diff[c - 'a']--;
for (int d : diff) if (abs(d) > 3) return false;
return true;
}JavaScript
var checkAlmostEquivalent = function(word1, word2) {
var diff = [];
for (var z = 0; z < 26; z++) diff.push(0);
for (var i = 0; i < word1.length; i++) diff[word1.charCodeAt(i) - 97]++;
for (var j = 0; j < word2.length; j++) diff[word2.charCodeAt(j) - 97]--;
for (var c = 0; c < 26; c++) if (Math.abs(diff[c]) > 3) return false;
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets