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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check Whether Two Strings are Almost Equivalent

Number: 2177

Difficulty: Easy

Paid? No

Companies: J.P. Morgan, Salesforce

Problem Description

Given two strings, word1 and word2, determine if they are almost equivalent. Two strings are considered almost equivalent if for every letter from 'a' to 'z', the absolute difference in frequency between the two strings is at most 3.

Key Insights

  • Count the frequency of each letter in both strings.
  • Compare the frequency counts letter by letter.
  • If the difference for any letter exceeds 3, the strings are not almost equivalent.
  • Since there are only 26 lowercase English letters, the solution operates in constant space with respect to the alphabet size.
  • Iteration over the string characters provides a linear time solution.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings. Space Complexity: O(1) (using fixed-size arrays for 26 letters).

Solution

We use two frequency arrays (or equivalent data structures) of size 26 to count the occurrences of each letter in word1 and word2, respectively. After counting, we iterate through both arrays and compare the frequencies. If the absolute difference exceeds 3 for any letter, we return false; otherwise, we return true. This approach ensures that our solution is efficient in both time and space.

Code Solutions

def are_almost_equivalent(word1, word2):
    # Create frequency arrays for 26 letters for both words
    freq1 = [0] * 26
    freq2 = [0] * 26
    
    # Count frequency of each letter in word1
    for char in word1:
        freq1[ord(char) - ord('a')] += 1
        
    # Count frequency of each letter in word2
    for char in word2:
        freq2[ord(char) - ord('a')] += 1
        
    # Check that the difference for each letter is at most 3
    for i in range(26):
        if abs(freq1[i] - freq2[i]) > 3:
            return False
    return True

# Example usage:
print(are_almost_equivalent("aaaa", "bccb"))  # Expected output: False
← Back to All Questions