We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check Whether Two Strings are Almost Equivalent

Difficulty: Easy

Problem Description

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.

Key Insights

  • Count the frequency of each character in both strings.
  • Compare the frequency difference for each character.
  • If any difference exceeds 3, return false; otherwise, return true.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (fixed size for the frequency array)

Solution

To solve the problem, we can use a frequency array to count the occurrences of each character for both strings. We then iterate through the alphabet (from 'a' to 'z') and check the absolute difference of counts from both strings. If any difference exceeds 3, we immediately return false. If we complete the checks without exceeding the limit, we return true.

Code Solutions

def areAlmostEquivalent(word1, word2):
    # Frequency arrays for both words
    freq1 = [0] * 26
    freq2 = [0] * 26
    
    # Count frequency of each character in word1
    for char in word1:
        freq1[ord(char) - ord('a')] += 1
    
    # Count frequency of each character in word2
    for char in word2:
        freq2[ord(char) - ord('a')] += 1
    
    # Check the frequency differences
    for i in range(26):
        if abs(freq1[i] - freq2[i]) > 3:
            return False
            
    return True
← Back to All Questions