Check Whether Two Strings are Almost Equivalent

Check Whether Two Strings are Almost Equivalent

What is this problem about?

Two strings of the same length are considered "almost equivalent" if the difference between the frequencies of every lowercase English letter ('a' to 'z') in both strings is at most 3. For example, if 'a' appears 5 times in string $s$ and 2 times in string $t$, the difference is 3, which is acceptable. If it appeared 6 times in $s$, the difference would be 4, and they would not be almost equivalent.

Why is this asked in interviews?

Companies like J.P. Morgan and Salesforce use this "Easy" problem to test your foundational skills in string manipulation and frequency counting. It’s a test of whether you can use a Hash Table or a fixed-size array to store counts efficiently. It evaluates your ability to iterate through a fixed set of keys (the alphabet) to verify a condition.

Algorithmic pattern used

The primary pattern is the Counting interview pattern using a Hash Table or Frequency Array. You create two frequency arrays of size 26 (one for each string). After counting the characters in both strings, you iterate through the 26 indices and check if $|count1[i] - count2[i]| \le 3$.

Example explanation

$s1 = "aaaa", s2 = "bccb"$

• Counts for $s1$: {a: 4}
• Counts for $s2$: {b: 2, c: 2}
• Difference for 'a': $|4 - 0| = 4$.
• 4 is greater than 3. Result: False. $s1 = "abcde", s2 = "bcdef"$
• All common letters (b, c, d, e) have difference 0.
• 'a' has diff 1, 'f' has diff 1. Result: True.

Common mistakes candidates make

The most common mistake is not checking every letter of the alphabet. Some candidates only check the letters present in one of the strings, forgetting that a letter present in $s1$ but not in $s2$ still contributes to the difference. Another mistake is using two nested loops to count characters, resulting in $O(N^2)$ instead of the optimal $O(N)$ approach.

Interview preparation tip

For any problem involving the difference between two sets of counts, try using a single frequency array. Increment the count for characters in the first string and decrement it for characters in the second string. At the end, simply check if every value in the array is between -3 and 3.