Vultr DocsLatest Content

Check Whether Two Strings are Almost Equivalent

Updated on 08 May, 2025
Check Whether Two Strings are Almost Equivalent header image

Problem Statement

In the context of this problem, two strings, word1 and word2, are referred to as almost equivalent if for each letter from 'a' to 'z', the absolute difference in their occurrences in both strings does not exceed 3. Formally, given the frequency of any letter 'x' in both strings, the problem requires checking if the absolute difference in frequency for each 'x' is at most 3. The task is to determine and return whether the two strings are almost equivalent. This means comparing their character frequencies across the entire alphabet and confirming that none surpass the given threshold difference.

Examples

Example 1

Input:

word1 = "aaaa", word2 = "bccb"

Output:

false

Explanation:

There are 4 'a's in "aaaa" but 0 'a's in "bccb".
The difference is 4, which is more than the allowed 3.

Example 2

Input:

word1 = "abcdeef", word2 = "abaaacc"

Output:

true

Explanation:

The differences between the frequencies of each letter in word1 and word2 are at most 3:
- 'a' appears 1 time in word1 and 4 times in word2. The difference is 3.
- 'b' appears 1 time in word1 and 1 time in word2. The difference is 0.
- 'c' appears 1 time in word1 and 2 times in word2. The difference is 1.
- 'd' appears 1 time in word1 and 0 times in word2. The difference is 1.
- 'e' appears 2 times in word1 and 0 times in word2. The difference is 2.
- 'f' appears 1 time in word1 and 0 times in word2. The difference is 1.

Example 3

Input:

word1 = "cccddabba", word2 = "babababab"

Output:

true

Explanation:

The differences between the frequencies of each letter in word1 and word2 are at most 3:
- 'a' appears 2 times in word1 and 4 times in word2. The difference is 2.
- 'b' appears 2 times in word1 and 5 times in word2. The difference is 3.
- 'c' appears 3 times in word1 and 0 times in word2. The difference is 3.
- 'd' appears 2 times in word1 and 0 times in word2. The difference is 2.

Constraints

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

Approach and Intuition

To determine if two strings are almost equivalent, we can adopt the following approach:

  1. Initialize a Frequency Count:

    • Begin by creating an array or a dictionary to count the frequency of each character from 'a' to 'z' for both word1 and word2.

  2. Fill Frequency Count:

    • Iterate through each character in word1 and increment its corresponding frequency count.
    • Simultaneously, decrement the frequency count for each character in word2. This step simplifies the process by converting the problem into finding any count in the array that exceeds 3 in absolute value (since incrementing for one string and decrementing for the other reflects the difference directly).

  3. Check for Maximum Allowed Difference:

    • After populating the frequency differences, iterate through the frequency array or dictionary.
    • If the absolute value of any frequency difference exceeds 3, return false since this indicates that the strings are not almost equivalent.
    • If the entire check completes without finding a exceeding difference, return true.

This method effectively utilizes counting and simple arithmetic to compare the strings, ensuring a time complexity primarily dependent on the length of the strings and the size of the alphabet (constant in this case, as it is limited to 26 letters). Thus, it is both efficient and straightforward given the constraints of the problem.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    bool areSimilar(string word1, string word2) {
        int frequency[26] = {0};

        for (int index = 0; index < word1.length(); index++) {
            frequency[word1[index] - 'a']++;
            frequency[word2[index] - 'a']--;
        }

        for (int index = 0; index < 26; index++) {
            if (std::abs(frequency[index]) > 3) {
                return false;
            }
        }

        return true;
    }
};

In this C++ solution, you check if two strings, 'word1' and 'word2', are "almost equivalent." The two strings are considered almost equivalent if, for every unique character, the difference in frequency between the two strings does not exceed three.

Follow these steps to understand the solution implementation:

  1. Initialize an array frequency of size 26 with all elements set to zero. This array is used to keep track of the frequency difference of each character ('a' to 'z') between the two strings.

  2. Loop through each character in word1 and word2. For each character in word1, increment the respective index in the frequency array based on the character's position in the alphabet. For each character in word2, decrement the respective index in the frequency array.

  3. After building the frequency array, loop through its elements. Check if the absolute value of any element in frequency is greater than 3. If such an element is found, return false as the strings are not almost equivalent.

  4. If no such condition is met in the previous step, return true indicating the strings are almost equivalent.

This method ensures efficient checking with a time complexity of O(n), where n is the length of the strings. Both strings must be of the same length, and only lowercase alphabetic characters are considered in this solution.

java 
class Solution {
    public boolean isAlmostEquivalent(String str1, String str2) {
        int[] lettersCount = new int[26];
        
        for (int i = 0; i < str1.length(); i++) {
            lettersCount[str1.charAt(i) - 'a']++;
            lettersCount[str2.charAt(i) - 'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (Math.abs(lettersCount[i]) > 3) {
                return false;
            }
        }
        
        return true;
    }
}

This Java solution determines if two strings, str1 and str2, are almost equivalent by checking the frequency of each letter in both strings. The method isAlmostEquivalent is defined to accomplish this check based on specific criteria. Follow this approach to understand the method's execution:

  1. Initialize an array lettersCount of size 26 to zero, which will hold the net difference in the count of each character between the two strings.

  2. Iterate through each character of the strings str1 and str2 by using the same index. For each character in str1, increment the corresponding index in lettersCount. For each character in str2, decrement the corresponding index in lettersCount.

  3. After processing both strings, loop through the lettersCount array to check the absolute differences of character counts:

    • If the absolute value of any count in lettersCount exceeds 3, the strings are not considered almost equivalent, and the function returns false.

  4. If the loop completes without finding a difference greater than 3, return true, indicating the strings are almost equivalent.

This method effectively tracks the character frequency discrepancies between the two strings, ensuring that the significant difference does not exceed three for any character, which is the criterion for the strings to be almost equivalent.

Comments

No comments yet.