algoadvance

Leetcode 2068. Check Whether Two Strings are Almost Equivalent

Problem Statement

Given two strings word1 and word2, a string word1 is almost equivalent to word2 if the differences between the frequencies of each character from a to z between word1 and word2 is at most 3. Formally, for all characters c, |frequency(c, word1) - frequency(c, word2)| <= 3.

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

Clarifying Questions

1. What are the constraints on the lengths of the strings? (Both word lengths are between 1 and 100, inclusive.)
2. Are the strings composed only of lowercase English letters? (Yes)

Strategy

1. Character Frequency Count: We’ll count the frequency of each character in both word1 and word2.
2. Comparison: We’ll then compare the frequency of each character. If the absolute difference at any point exceeds 3, we’ll return false.
3. Initialization: Use two arrays of size 26 (for each letter of the alphabet) to store the character frequencies of word1 and word2.
4. Efficiency: This approach ensures linear time complexity, O(n), where n is the length of the longest string since the counting is done in a single pass through each string.

Code

#include <iostream>
#include <vector>
#include <cmath> // for abs

bool checkAlmostEquivalent(std::string word1, std::string word2) {
    std::vector<int> freq1(26, 0); // Frequency array for word1
    std::vector<int> freq2(26, 0); // Frequency array for word2

    // Count character frequencies for word1
    for(char c : word1) {
        freq1[c - 'a']++;
    }

    // Count character frequencies for word2
    for(char c : word2) {
        freq2[c - 'a']++;
    }

    // Check the absolute difference in frequencies
    for(int i = 0; i < 26; i++) {
        if(std::abs(freq1[i] - freq2[i]) > 3) {
            return false;
        }
    }

    return true;
}

int main() {
    std::string word1 = "aabbcc";
    std::string word2 = "abbbccc";
    bool result = checkAlmostEquivalent(word1, word2);
    std::cout << (result ? "True" : "False") << std::endl;
    return 0;
}

Explanation

• Frequency Arrays: We use freq1 and freq2 to keep track of the frequencies of characters in word1 and word2.
• Counting Frequencies: Iterate through each character in word1 and word2, updating the respective frequency array.
• Checking Differences: Loop through the frequency arrays, comparing the frequencies of corresponding characters. If any character’s frequency difference exceeds 3, return false.
• Final Check: If no differences exceed 3, return true.

Time Complexity

The time complexity of this solution is O(n + m), where n is the length of word1 and m is the length of word2. This is because:

• We traverse each string once to count character frequencies (O(n) for word1 and O(m) for word2).
• We then perform a constant-time check over the fixed-size frequency arrays (26 elements), which is O(26) or simply O(1).

In conclusion, the overall complexity is linear with respect to the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?