Check Whether Two Strings are Almost Equivalent

In this problem, we are trying to check if two strings are almost equivalent. We will compare the frequencies of each character in both strings. The two strings are almost equivalent if the difference of the frequencies of each character is at most 3.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        # Define a dictionary to store character frequencies
        freq1 = [0]*26
        freq2 = [0]*26

        # Calculate frequencies of characters in word1
        for char in word1:
            freq1[ord(char) - ord('a')] += 1

        # Calculate frequencies of characters in word2
        for char in word2:
            freq2[ord(char) - ord('a')] += 1

        # Check if the difference of frequencies of each character is at most 3
        for i in range(26):
            if abs(freq1[i] - freq2[i]) > 3:
                return False
        return True

In the code:

1. We first initialize two frequency arrays freq1 and freq2 of size 26 (as there are 26 lowercase English letters) to 0.

2. We then iterate over each character in word1 and word2, incrementing the corresponding index in the frequency array.

3. Finally, we check if the absolute difference of frequencies for each character in the two words is more than 3. If we find such a character, we return False. If no such character is found, we return True.

This solution leverages the frequency counting technique and comparison between two frequency arrays, which are the basic building blocks of this problem.

The basic building blocks of this solution are:

1. Frequency Counting: The frequency of each character in both strings is calculated and stored in arrays. This technique is common in problems dealing with character or element occurrence in strings or arrays.

2. Array Comparison: After calculating the frequencies, we compare the two frequency arrays. In this problem, we are checking if the absolute difference of the frequencies of each corresponding character is more than 3.

3. Use of ASCII Values: To index the frequency array, the ASCII values of the characters are used. This technique is common when we need to map characters to specific indexes in an array.

4. Iteration: The solution iterates over the characters in the strings to calculate the frequencies, and over the frequency arrays to make the comparison. This is a basic block that involves scanning or traversing the data.

5. Condition Check: A conditional check (abs(freq1[i] - freq2[i]) > 3) is used to determine if the frequency difference is more than the allowed limit. If it is, we immediately return False.

These building blocks together form the solution to check if two strings are almost equivalent.