Check Whether Two Strings are Almost Equivalent

Difficulty: Easy | Acceptance: 64.30% | Paid: No Topics: Hash Table, String, Counting

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.

• Examples
• Constraints
• Frequency Array
• Hash Map
• Single Pass

Examples

Example 1

Input: word1 = "aaaa", word2 = "bccb"
Output: false
Explanation: The differences in frequencies are:
- 'a': 4 - 0 = 4
- 'b': 0 - 2 = -2
- 'c': 0 - 2 = -2
The difference for 'a' is 4, which is greater than 3.

Example 2

Input: word1 = "abcdeef", word2 = "abaaacc"
Output: true
Explanation: The differences in frequencies are:
- 'a': 1 - 3 = -2
- 'b': 1 - 1 = 0
- 'c': 1 - 2 = -1
- 'd': 1 - 0 = 1
- 'e': 2 - 0 = 2
- 'f': 1 - 0 = 1
All differences are at most 3.

Example 3

Input: word1 = "zzzzzzzzzzzzzzzzzzzz", word2 = "zzzzzzzzzzzzzzzzzzzz"
Output: true

Constraints

n == word1.length == word2.length
1 <= n <= 100
word1 and word2 consist only of lowercase English letters.

Frequency Array

Intuition Use a fixed-size array of 26 elements to track the frequency difference between the two strings for each letter.

Steps

• Initialize an array of 26 integers with zeros
• Iterate through word1 and increment the count for each character
• Iterate through word2 and decrement the count for each character
• Check if any absolute value in the array exceeds 3

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        freq = [0] * 26
        for c in word1:
            freq[ord(c) - ord('a')] += 1
        for c in word2:
            freq[ord(c) - ord('a')] -= 1
        for f in freq:
            if abs(f) > 3:
                return False
        return True

Complexity

• Time: O(n) where n is the length of the strings
• Space: O(1) since we use a fixed-size array of 26 elements
• Notes: Most efficient approach for lowercase English letters

Hash Map

Intuition Use a hash map to track the frequency difference between the two strings, only storing entries for characters that appear.

Steps

• Create an empty hash map
• Iterate through word1 and increment the count for each character
• Iterate through word2 and decrement the count for each character
• Check if any absolute value in the map exceeds 3

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        freq = {}
        for c in word1:
            freq[c] = freq.get(c, 0) + 1
        for c in word2:
            freq[c] = freq.get(c, 0) - 1
        for f in freq.values():
            if abs(f) > 3:
                return False
        return True

Complexity

• Time: O(n) where n is the length of the strings
• Space: O(k) where k is the number of unique characters (at most 26)
• Notes: More flexible than array approach but slightly slower due to hash operations

Single Pass

Intuition Process both strings simultaneously in a single pass, updating the frequency difference array as we go.

Steps

• Initialize an array of 26 integers with zeros
• Iterate through both strings at the same time
• Increment for the character from word1 and decrement for the character from word2
• Check if any absolute value in the array exceeds 3

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        freq = [0] * 26
        for c1, c2 in zip(word1, word2):
            freq[ord(c1) - ord('a')] += 1
            freq[ord(c2) - ord('a')] -= 1
        for f in freq:
            if abs(f) > 3:
                return False
        return True

Complexity

• Time: O(n) where n is the length of the strings
• Space: O(1) since we use a fixed-size array of 26 elements
• Notes: Slightly more cache-friendly as it processes both strings in one loop