algoadvance

Given two strings word1 and word2, they are considered almost equivalent if the following condition is satisfied:

For every character ch in the set of characters of word1 ∪ word2, the absolute difference between the number of occurrences of ch in word1 and word2 is at most 3.

Return true if word1 and word2 are almost equivalent, or false otherwise.

Clarifying Questions

1. Should the comparison be case-sensitive?
   • Yes, characters should be considered case-sensitive.
2. What is the allowed length for word1 and word2?
   • The lengths of word1 and word2 are not specified, but usual constraints for string problems like this on LeetCode fall within a manageable range for algorithms needing O(n) time complexity.

Strategy

1. Create a frequency counter for each string using Python’s collections.Counter.
2. For each character in the union of the sets of characters from both strings, compute the absolute difference in their counts from word1 and word2.
3. If any character’s count difference exceeds 3, return false.
4. If all differences are within the acceptable range, return true.

Code

from collections import Counter

def checkAlmostEquivalent(word1: str, word2: str) -> bool:
    # Count character frequencies for both words
    counter1 = Counter(word1)
    counter2 = Counter(word2)
    
    # Get the union of keys from both counters
    all_chars = set(counter1.keys()).union(set(counter2.keys()))
    
    # Check the absolute difference for each character
    for ch in all_chars:
        if abs(counter1.get(ch, 0) - counter2.get(ch, 0)) > 3:
            return False
    
    return True

# Example usage
word1 = "acbdeab"
word2 = "abcdedcbf"
print(checkAlmostEquivalent(word1, word2))  # Output: True

Time Complexity

• Counting the frequency of each character in both strings: O(n + m), where n is the length of word1 and m is the length of word2.
• Constructing the union set of characters: O(u), where u is the total number of unique characters from both strings combined. However, u is at most 26 for lowercase letters in the Latin alphabet.
• Iterating over the set of unique characters to check differences: O(u).
• Therefore, the total time complexity is O(n + m).

Space Complexity

• We use two Counter objects to store the frequency of each character in word1 and word2, which will each require space proportional to the number of unique characters, resulting in a space complexity of O(u).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?