Check Whether Two Strings are Almost Equivalent

Easy

#1883Time: 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.3 companies

Patterns

Counting

Data structures

Hash Table String

Companies

J.P. Morgan Salesforce Vanguard

Prompt

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.length
1 <= n <= 100
word1 and word2 consist 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 c from 'a' to 'z'.
For each character c, initialize two counters, count1 and count2, to zero.
Traverse the first string, word1, and increment count1 for each occurrence of c.
Traverse the second string, word2, and increment count2 for each occurrence of c.
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 false immediately.
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.

1class Solution {2    public boolean checkAlmostEquivalent(String word1, String word2) {3        for (char c = 'a'; c <= 'z'; c++) {4            int count1 = 0;5            for (int i = 0; i < word1.length(); i++) {6                if (word1.charAt(i) == c) {7                    count1++;8                }9            }10 11            int count2 = 0;12            for (int i = 0; i < word2.length(); i++) {13                if (word2.charAt(i) == c) {14                    count2++;15                }16            }17 18            if (Math.abs(count1 - count2) > 3) {19                return false;20            }21        }22        return true;23    }24}

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.

A more efficient approach is to first compute the frequency of all characters in each string and store them. Hash maps are a suitable data structure for this task. We can iterate through each string once to build its frequency map. After populating the maps, we can iterate through the alphabet and compare the frequencies from the two maps to check the condition.

Algorithm

Create two HashMap<Character, Integer>, freq1 and freq2, to store character frequencies.
Iterate through word1. For each character, update its count in freq1.
Iterate through word2. For each character, update its count in freq2.
Iterate through all characters c from 'a' to 'z'.
For each c, get its frequency from freq1 and freq2, using getOrDefault to handle cases where the character is not present (which defaults to 0).
Calculate the absolute difference of these frequencies.
If the difference is greater than 3, return false.
If the loop finishes, return true.

Walkthrough

This method avoids the redundant scanning of the brute-force approach. First, we create two hash maps. The first map, freq1, is populated by iterating through word1 and storing the count of each character. The second map, freq2, is populated similarly from word2. Once both maps are ready, we iterate from 'a' to 'z'. For each character, we look up its count in both maps (if a character is absent, its count is 0). We then check if the absolute difference of the counts exceeds 3. If it does, we return false. If we iterate through all 26 letters without this condition being met, we return true.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean checkAlmostEquivalent(String word1, String word2) {6        Map<Character, Integer> freq1 = new HashMap<>();7        for (char c : word1.toCharArray()) {8            freq1.put(c, freq1.getOrDefault(c, 0) + 1);9        }10 11        Map<Character, Integer> freq2 = new HashMap<>();12        for (char c : word2.toCharArray()) {13            freq2.put(c, freq2.getOrDefault(c, 0) + 1);14        }15 16        for (char c = 'a'; c <= 'z'; c++) {17            int count1 = freq1.getOrDefault(c, 0);18            int count2 = freq2.getOrDefault(c, 0);19            if (Math.abs(count1 - count2) > 3) {20                return false;21            }22        }23 24        return true;25    }26}

Complexity

Time

O(n), where `n` is the length of the strings. We traverse each string once to build the maps (`O(n) + O(n)`) and then iterate through the 26 letters of the alphabet (`O(1)`). The total time is O(n).

Space

O(k), where `k` is the size of the alphabet (26). Since `k` is constant, the space complexity is O(1). We use two maps, each storing at most 26 key-value pairs.

Trade-offs

Pros

Much more efficient than the brute-force approach as it avoids repeated string traversals.
A general solution that would work even if the character set was not fixed or known in advance.

Cons

Using HashMap introduces some overhead compared to a simple array, both in terms of memory and time (due to hashing and potential collisions).
Slightly more complex to implement than the brute-force approach.

Since the problem specifies that the strings contain only lowercase English letters, we can use a more optimized data structure than a hash map: a simple array of size 26. Each index in the array corresponds to a letter of the alphabet (e.g., index 0 for 'a', 1 for 'b', etc.). This approach is similar to using hash maps but is generally faster and more memory-efficient for a fixed, small character set.

Algorithm

Create two integer arrays, counts1 and counts2, each of size 26, initialized to all zeros.
Iterate through word1. For each character c, increment the count at index c - 'a' in counts1.
Iterate through word2. For each character c, increment the count at index c - 'a' in counts2.
Iterate from i = 0 to 25.
For each index i, calculate the absolute difference Math.abs(counts1[i] - counts2[i]).
If this difference is greater than 3, return false.
If the loop completes, return true.

Walkthrough

This approach replaces hash maps with arrays for efficiency. We declare two integer arrays, counts1 and counts2, of size 26. We traverse word1, and for each character, we increment the corresponding index in counts1. For example, if we see 'c', we increment counts1[2]. We do the same for word2 and counts2. After counting, we loop through the arrays from index 0 to 25, comparing the elements at each index (e.g., counts1[i] vs counts2[i]). If the absolute difference at any index is greater than 3, we return false. If the loop finishes, we return true.

1class Solution {2    public boolean checkAlmostEquivalent(String word1, String word2) {3        int[] counts1 = new int[26];4        for (char c : word1.toCharArray()) {5            counts1[c - 'a']++;6        }7 8        int[] counts2 = new int[26];9        for (char c : word2.toCharArray()) {10            counts2[c - 'a']++;11        }12 13        for (int i = 0; i < 26; i++) {14            if (Math.abs(counts1[i] - counts2[i]) > 3) {15                return false;16            }17        }18 19        return true;20    }21}

Complexity

Time

O(n), where `n` is the length of the strings. We perform two passes over the strings (`O(n) + O(n)`) and one pass over the frequency arrays (`O(1)`). The total time is O(n).

Space

O(k), where `k` is the size of the alphabet (26). Since `k` is constant, this is O(1). We use two arrays of size 26.

Trade-offs

Pros

Very efficient in both time and space for a fixed alphabet.
Faster than the hash map approach due to direct array indexing which avoids hashing overhead.

Cons

Less general than the hash map approach; it's specifically tailored to a known, small character set like lowercase English letters.

We can further optimize the previous approach by using only one frequency array instead of two. We can iterate through the first string and increment the counts, then iterate through the second string and decrement the counts in the same array. The resulting array will directly hold the difference in frequencies for each character, which we can then check against the threshold of 3.

Algorithm

Create a single integer array, counts, of size 26, initialized to all zeros.
Since word1 and word2 have the same length, iterate from i = 0 to n-1 (where n is the length).
In each iteration, increment the count for the character from word1 and decrement the count for the character from word2 in the counts array.
After the loop, counts[j] will store the difference in frequencies for the j-th letter of the alphabet.
Iterate through the counts array.
For each value diff in the array, check if Math.abs(diff) > 3.
If the condition is met for any character, return false.
If the loop completes, return true.

Walkthrough

This is the most optimized solution. It uses a single integer array, counts, of size 26. We can make a single pass through the strings, since they are of equal length. In each step of the loop, we take a character from word1 and increment its corresponding counter in counts. Simultaneously, we take the character at the same position from word2 and decrement its counter. For example, counts[word1.charAt(i) - 'a']++ and counts[word2.charAt(i) - 'a']--. After this single pass, the counts array will contain the final difference for each character's frequency. Finally, we iterate through this counts array and check if the absolute value of any element exceeds 3. If it does, we return false. Otherwise, we return true.

1class Solution {2    public boolean checkAlmostEquivalent(String word1, String word2) {3        int[] counts = new int[26];4        for (int i = 0; i < word1.length(); i++) {5            counts[word1.charAt(i) - 'a']++;6            counts[word2.charAt(i) - 'a']--;7        }8 9        for (int count : counts) {10            if (Math.abs(count) > 3) {11                return false;12            }13        }14 15        return true;16    }17}

Complexity

Time

O(n), where `n` is the length of the strings. We iterate through the strings once (`O(n)`) and then iterate through the frequency array (`O(1)`). The total time is O(n).

Space

O(k), where `k` is the size of the alphabet (26). Since `k` is constant, this is O(1). This is the most space-efficient approach as it uses only one array.

Trade-offs

Pros

Most efficient in terms of space, using only a single array of size 26.
Very fast due to a single pass over the strings and direct array access.
Clean and concise implementation.

Cons

Like the two-array approach, it's tailored to a fixed character set and is not a general-purpose solution for all character types.

Solutions

Solution

1public class Solution {2    public bool CheckAlmostEquivalent(string word1, string word2) {3        int[] cnt = new int[26];4        foreach(var c in word1) {5            cnt[c - 'a']++;6        }7        foreach(var c in word2) {8            cnt[c - 'a']--;9        }10        return cnt.All(x => Math.Abs(x) <= 3);11    }12}

1class Solution {2public3  boolean checkAlmostEquivalent(String word1, String word2) {4    int[] cnt = new int[26];5    for (int i = 0; i < word1.length(); ++i) {6      ++cnt[word1.charAt(i) - 'a'];7    }8    for (int i = 0; i < word2.length(); ++i) {9      --cnt[word2.charAt(i) - 'a'];10    }11    for (int x : cnt) {12      if (Math.abs(x) > 3) {13        return false;14      }15    }16    return true;17  }18}

1/** * @param {string} word1 * @param {string} word2 * @return {boolean} */ var checkAlmostEquivalent =2  function (word1, word2) {3    const m = new Map();4    for (let i = 0; i < word1.length; i++) {5      m.set(word1[i], (m.get(word1[i]) || 0) + 1);6      m.set(word2[i], (m.get(word2[i]) || 0) - 1);7    }8    for (const v of m.values()) {9      if (Math.abs(v) > 3) {10        return false;11      }12    }13    return true;14  };

1class Solution {2public:3  bool checkAlmostEquivalent(string word1, string word2) {4    int cnt[26]{};5    for (char &c : word1) {6      ++cnt[c - 'a'];7    }8    for (char &c : word2) {9      --cnt[c - 'a'];10    }11    for (int i = 0; i < 26; ++i) {12      if (abs(cnt[i]) > 3) {13        return false;14      }15    }16    return true;17  }18};

1class Solution:2    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())

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.

← Previous

Previous problem

Next problem

Solution

1public class Solution {2    public bool CheckAlmostEquivalent(string word1, string word2) {3        int[] cnt = new int[26];4        foreach(var c in word1) {5            cnt[c - 'a']++;6        }7        foreach(var c in word2) {8            cnt[c - 'a']--;9        }10        return cnt.All(x => Math.Abs(x) <= 3);11    }12}

1class Solution {2public3  boolean checkAlmostEquivalent(String word1, String word2) {4    int[] cnt = new int[26];5    for (int i = 0; i < word1.length(); ++i) {6      ++cnt[word1.charAt(i) - 'a'];7    }8    for (int i = 0; i < word2.length(); ++i) {9      --cnt[word2.charAt(i) - 'a'];10    }11    for (int x : cnt) {12      if (Math.abs(x) > 3) {13        return false;14      }15    }16    return true;17  }18}

1/** * @param {string} word1 * @param {string} word2 * @return {boolean} */ var checkAlmostEquivalent =2  function (word1, word2) {3    const m = new Map();4    for (let i = 0; i < word1.length; i++) {5      m.set(word1[i], (m.get(word1[i]) || 0) + 1);6      m.set(word2[i], (m.get(word2[i]) || 0) - 1);7    }8    for (const v of m.values()) {9      if (Math.abs(v) > 3) {10        return false;11      }12    }13    return true;14  };

1class Solution {2public:3  bool checkAlmostEquivalent(string word1, string word2) {4    int cnt[26]{};5    for (char &c : word1) {6      ++cnt[c - 'a'];7    }8    for (char &c : word2) {9      --cnt[c - 'a'];10    }11    for (int i = 0; i < 26; ++i) {12      if (abs(cnt[i]) > 3) {13        return false;14      }15    }16    return true;17  }18};

1class Solution:2    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())

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.