# Check Whether Two Strings are Almost Equivalent
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-whether-two-strings-are-almost-equivalent)
Canonical: https://scaleengineer.com/dsa/problems/check-whether-two-strings-are-almost-equivalent
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Salesforce](https://scaleengineer.com/companies/salesforce), [Vanguard](https://scaleengineer.com/companies/vanguard)
---
## Problem
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
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Frequency Counting with Two Hash Maps
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.
**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.
**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.
### Explanation
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`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        Map<Character, Integer> freq1 = new HashMap<>();
        for (char c : word1.toCharArray()) {
            freq1.put(c, freq1.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> freq2 = new HashMap<>();
        for (char c : word2.toCharArray()) {
            freq2.put(c, freq2.getOrDefault(c, 0) + 1);
        }

        for (char c = 'a'; c <= 'z'; c++) {
            int count1 = freq1.getOrDefault(c, 0);
            int count2 = freq2.getOrDefault(c, 0);
            if (Math.abs(count1 - count2) > 3) {
                return false;
            }
        }

        return true;
    }
}
```
### 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`.

## Frequency Counting with Two Arrays
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        int[] counts1 = new int[26];
        for (char c : word1.toCharArray()) {
            counts1[c - 'a']++;
        }

        int[] counts2 = new int[26];
        for (char c : word2.toCharArray()) {
            counts2[c - 'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (Math.abs(counts1[i] - counts2[i]) > 3) {
                return false;
            }
        }

        return true;
    }
}
```
### 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`.

## Optimized Frequency Counting with a Single Array
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        int[] counts = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            counts[word1.charAt(i) - 'a']++;
            counts[word2.charAt(i) - 'a']--;
        }

        for (int count : counts) {
            if (Math.abs(count) > 3) {
                return false;
            }
        }

        return true;
    }
}
```
### 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`.

# Solutions
### CSharp

```csharp
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);
    }
}
```

### Java

```java
class Solution {
public
  boolean checkAlmostEquivalent(String word1, String word2) {
    int[] cnt = new int[26];
    for (int i = 0; i < word1.length(); ++i) {
      ++cnt[word1.charAt(i) - 'a'];
    }
    for (int i = 0; i < word2.length(); ++i) {
      --cnt[word2.charAt(i) - 'a'];
    }
    for (int x : cnt) {
      if (Math.abs(x) > 3) {
        return false;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {string} word1 * @param {string} word2 * @return {boolean} */ var checkAlmostEquivalent =
  function (word1, word2) {
    const m = new Map();
    for (let i = 0; i < word1.length; i++) {
      m.set(word1[i], (m.get(word1[i]) || 0) + 1);
      m.set(word2[i], (m.get(word2[i]) || 0) - 1);
    }
    for (const v of m.values()) {
      if (Math.abs(v) > 3) {
        return false;
      }
    }
    return true;
  };

```

### CPP

```cpp
class Solution {
public:
  bool checkAlmostEquivalent(string word1, string word2) {
    int cnt[26]{};
    for (char &c : word1) {
      ++cnt[c - 'a'];
    }
    for (char &c : word2) {
      --cnt[c - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (abs(cnt[i]) > 3) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    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())

```