Leetcode 2068: Check Whether Two Strings are Almost Equivalent

Input: Two strings of equal length `n` are provided as input. Each string consists of lowercase English letters.

Example: word1 = "abcd", word2 = "abdc"

Constraints:

• 1 <= n <= 100

• Both word1 and word2 consist only of lowercase English letters.

Output: Return `true` if the two strings are almost equivalent, otherwise return `false`.

Example: true

Constraints:

Goal: Check if the absolute frequency difference for each letter in the two strings is at most 3.

Steps:

• Count the frequency of each letter in both strings.

• Calculate the absolute difference of the frequencies for each letter.

• If any difference exceeds 3, return false; otherwise, return true.

Goal: The length of the input strings will not exceed 100 characters, and they will only contain lowercase English letters.

Steps:

• 1 <= n <= 100

• word1 and word2 consist only of lowercase English letters.

Assumptions:

• Both input strings are of equal length.

• Input: word1 = "abcd", word2 = "abdc"

• Explanation: Both strings have identical characters, and the frequency difference for each letter is 0, which is within the allowed limit.

• Input: word1 = "zzzz", word2 = "aaabb"

• Explanation: The difference in the frequency of 'z' is 4, which exceeds the allowed limit of 3.

Approach: Count the frequency of each character in both strings, compute the difference in their frequencies, and check if any difference exceeds 3.

Observations:

• Both strings should be of the same length.

• We need to compare the frequencies of each character.

• An efficient solution would involve counting the frequencies of characters and comparing the differences for each letter.

Steps:

• Initialize an array to store the frequency count for each character in `word1` and `word2`.

• Calculate the absolute difference in frequency for each character from 'a' to 'z'.

• Return false if any difference exceeds 3, otherwise return true.

Empty Inputs:

• If either string is empty, the function should return true.

Large Inputs:

• If the strings are at their maximum length (100), ensure that the solution works within the time constraints.

Special Values:

• If the strings are identical, the function should return true.

Constraints:

• Both strings must be the same length.

bool checkAlmostEquivalent(string s, string t) {
    int cnt[26] = {};
    for (char c : s) cnt[c - 'a']++;
    for (char c : t) cnt[c - 'a']--;
    for (int i = 0; i < 26; ++i) {
        if (abs(cnt[i]) > 3) return false;
    }
    return true;
}

1 : Function Definition

bool checkAlmostEquivalent(string s, string t) {

This line defines the function `checkAlmostEquivalent` that takes two strings as input and returns a boolean value.

2 : Array Initialization

    int cnt[26] = {};

An array `cnt` of size 26 is initialized to store the frequency of each letter in the input strings. The array is initialized with zero values.

3 : Count Characters in s

    for (char c : s) cnt[c - 'a']++;

This loop iterates through each character in string `s` and increments the corresponding index in the `cnt` array based on the character's ASCII value.

4 : Count Characters in t

    for (char c : t) cnt[c - 'a']--;

This loop iterates through each character in string `t` and decrements the corresponding index in the `cnt` array.

5 : Loop Over All Characters

    for (int i = 0; i < 26; ++i) {

This loop checks all indices of the `cnt` array (corresponding to each letter of the alphabet).

6 : Check Difference Exceeds 3

        if (abs(cnt[i]) > 3) return false;

If the absolute value of the count at any index in the `cnt` array exceeds 3, the function returns `false`, indicating the strings are not almost equivalent.

7 : Return True

    return true;

If no character's frequency difference exceeds 3, the function returns `true`, indicating the strings are almost equivalent.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear, as we iterate over each string once.

Best Case: O(1)

Worst Case: O(1)

Description: We use constant space, as we only need an array of size 26 to store character frequencies.

Leetcode 2068: Check Whether Two Strings are Almost Equivalent

Explore →