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 <= 100word1 and word2 consist only of lowercase English letters.In #2068 Check Whether Two Strings are Almost Equivalent, the goal is to compare two strings and ensure that the difference in frequency of every character does not exceed a specific threshold. Since the strings contain lowercase English letters, an efficient way to solve the problem is by counting character frequencies.
A common approach is to maintain a frequency structure such as a hash table or a fixed-size array of length 26. First, iterate through both strings and track how many times each character appears. After building the frequency counts, compare the counts for each character and compute the absolute difference.
If the difference for any character exceeds the allowed limit, the strings are not almost equivalent. Otherwise, they satisfy the condition. Because the alphabet size is constant, the comparison step remains very efficient. This approach avoids unnecessary nested loops and ensures a clean linear scan of the input.
The method runs in O(n) time with constant auxiliary space due to the fixed alphabet size.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Frequency Counting using Array/Hash Table | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
What data structure can we use to count the frequency of each character?
Are there edge cases where a character is present in one string but not the other?
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.
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.
1using System;
2
3public class Solution {
4 public bool AreAlmostEquivalent(string word1, string word2) {
5 int[] freq1 = new int[26];
6 int[] freq2 = new int[26];
7
8 for (int i = 0; i < word1.Length; i++) {
9 freq1[word1[i] - 'a']++;
10 freq2[word2[i] - 'a']++;
11 }
12
13 for (int i = 0; i < 26; i++) {
14 if (Math.Abs(freq1[i] - freq2[i]) > 3) {
return false;
}
}
return true;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.AreAlmostEquivalent("abcdeef", "abaaacc"));
}
}The C# solution employs a similar mechanism as other solutions, using arrays to track character occurrences. The final check ensures no frequency difference exceeds 3.
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.
Time Complexity: O(n), limited by character frequency computation.
Space Complexity: O(1), determined by number of distinct characters, since max 26 distinct alphabets.
1def are_almost_equivalent
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving string frequency counting and hash tables are common in FAANG-style interviews. While this exact problem may vary, the concept of comparing character frequencies efficiently is a frequently tested pattern.
A fixed-size array of length 26 is usually the best data structure because the input consists of lowercase English letters. It provides constant-time access and uses minimal memory compared to a generic hash map.
The optimal approach uses frequency counting for each character in both strings. By storing counts in an array of size 26 or a hash map and comparing the absolute difference for every character, we can quickly determine if the strings are almost equivalent in linear time.
The time complexity is O(n), where n is the length of the strings. We scan both strings to count character frequencies and then compare counts across the 26 possible characters.
Using Python's defaultdict, this solution accumulates frequencies of each character in two dictionaries. It defaults to integers unlike regular dictionaries requiring initialization. The condition for 'almost equivalence' checks frequency differences not surpassing 3.