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 ifword1 and word2 arealmost equivalent , or false otherwise.

The frequency of a letter x is the number of times it occurs in the string.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7

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.

Solution

Method 1 – Frequency Counting

Intuition

We need to compare the frequency of each letter in both strings and ensure the difference for every letter is at most 3. This is a direct frequency counting problem.

Reasoning

By counting the occurrences of each letter in both strings, we can compare the absolute difference for each letter. If all differences are at most 3, the strings are almost equivalent.

Approach

  1. Initialize two arrays of size 26 to count the frequency of each letter in word1 and word2.
  2. Iterate through both strings and update the frequency arrays.
  3. For each letter from ‘a’ to ‘z’, check if the absolute difference in frequencies is at most 3.
  4. Return true if all differences are at most 3, otherwise false.

Edge cases:

  • Both strings are identical.
  • One string has a letter that the other does not.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

func checkAlmostEquivalent(word1, word2 string) bool {
    cnt1, cnt2 := [26]int{}, [26]int{}
    for _, c := range word1 {
        cnt1[c-'a']++
    }
    for _, c := range word2 {
        cnt2[c-'a']++
    }
    for i := 0; i < 26; i++ {
        if abs(cnt1[i]-cnt2[i]) > 3 {
            return false
        }
    }
    return true
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

class Solution {
    fun checkAlmostEquivalent(word1: String, word2: String): Boolean {
        val cnt1 = IntArray(26)
        val cnt2 = IntArray(26)
        for (c in word1) cnt1[c - 'a']++
        for (c in word2) cnt2[c - 'a']++
        for (i in 0 until 26) {
            if (kotlin.math.abs(cnt1[i] - cnt2[i]) > 3) return false
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def check_almost_equivalent(self, word1: str, word2: str) -> bool:
        cnt1 = [0] * 26
        cnt2 = [0] * 26
        for c in word1:
            cnt1[ord(c) - ord('a')] += 1
        for c in word2:
            cnt2[ord(c) - ord('a')] += 1
        for i in range(26):
            if abs(cnt1[i] - cnt2[i]) > 3:
                return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn check_almost_equivalent(word1: String, word2: String) -> bool {
        let mut cnt1 = [0; 26];
        let mut cnt2 = [0; 26];
        for c in word1.chars() {
            cnt1[(c as u8 - b'a') as usize] += 1;
        }
        for c in word2.chars() {
            cnt2[(c as u8 - b'a') as usize] += 1;
        }
        for i in 0..26 {
            if (cnt1[i] - cnt2[i]).abs() > 3 {
                return false;
            }
        }
        true
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we scan both strings and compare frequencies for all 26 letters.
  • 🧺 Space complexity: O(1), as the frequency arrays are of fixed size.