Check Whether Two Strings are Almost Equivalent
EasyPrompt
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.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's definition into code. It iterates through every letter of the alphabet from 'a' to 'z'. For each letter, it performs a full scan of both word1 and word2 to count its occurrences. Then, it calculates the difference and checks if it exceeds the threshold of 3.
Algorithm
- Iterate through each character
cfrom 'a' to 'z'. - For each character
c, initialize two counters,count1andcount2, to zero. - Traverse the first string,
word1, and incrementcount1for each occurrence ofc. - Traverse the second string,
word2, and incrementcount2for each occurrence ofc. - After counting, calculate the absolute difference:
Math.abs(count1 - count2). - If the difference is greater than 3, the strings are not almost equivalent, so return
falseimmediately. - If the loop completes for all 26 characters without returning, it means the condition holds for all letters. Return
true.
Walkthrough
The algorithm works by checking each character of the alphabet one by one. For a given character, say 'a', it first counts how many 'a's are in word1 by looping through it. Then, it does the same for word2. Finally, it compares these two counts. If the absolute difference is more than 3, we know the strings are not almost equivalent and can stop and return false. If the difference is within the limit, we proceed to the next character, 'b', and repeat the process. If we successfully check all characters from 'a' to 'z' without finding a difference greater than 3, we can conclude the strings are almost equivalent and return true.
class Solution { public boolean checkAlmostEquivalent(String word1, String word2) { for (char c = 'a'; c <= 'z'; c++) { int count1 = 0; for (int i = 0; i < word1.length(); i++) { if (word1.charAt(i) == c) { count1++; } } int count2 = 0; for (int i = 0; i < word2.length(); i++) { if (word2.charAt(i) == c) { count2++; } } if (Math.abs(count1 - count2) > 3) { return false; } } return true; }}Complexity
Time
O(k * n), where `k` is the number of unique characters in the alphabet (26) and `n` is the length of the strings. Since `k` is a constant, the complexity simplifies to O(n). However, it involves traversing the strings 26 times, making it less efficient in practice than other O(n) solutions.
Space
O(1), as we only use a few variables to store the counts for the current character being checked.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem statement.
Requires no extra data structures, resulting in O(1) space complexity.
Cons
Highly inefficient due to repeated traversals of the input strings. For each of the 26 letters, it scans both strings completely, leading to a high constant factor in its time complexity.
Solutions
Solution
public class Solution { public bool CheckAlmostEquivalent(string word1, string word2) { int[] cnt = new int[26]; foreach(var c in word1) { cnt[c - 'a']++; } foreach(var c in word2) { cnt[c - 'a']--; } return cnt.All(x => Math.Abs(x) <= 3); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.