IBM Coding Assessment Question | Similar Strings Based on Character Frequency Difference ≤ 3

I encountered this problem in an IBM Coding Assessment and found the frequency-counting observation quite straightforward but interesting. Sharing it here for others preparing for IBM coding assessments and DSA interviews.

Problem Statement

You are given two arrays of strings, s and t, each of length n.

Each pair s[i] and t[i] contains two lowercase English strings.

Two strings are considered similar if, for every lowercase English letter from 'a' to 'z', the absolute difference between the number of occurrences of that letter in the two strings is at most 3.

In other words, for every character x:

abs(count(s[i], x) - count(t[i], x)) <= 3

Your task is to check every corresponding pair s[i] and t[i].

Return an array where:

"YES" means the pair is similar. "NO" means the pair is not similar.

Example

Suppose we have two pairs of strings.

For the first pair, after counting the characters, we get something like:

Letter Count in s Count in t Difference a 4 1 3 b 2 4 2 c 0 1 1

Since every difference is at most 3, this pair is similar.

For the second pair:

Letter Count in s Count in t Difference a 5 1 4 b 2 6 4

Here the difference is greater than 3, so this pair is not similar.

Therefore, the output can be:

["YES", "NO"]

Key Observation

We don't need to compare the strings character‑by‑character.

The condition only depends on the frequency of each lowercase English letter.

Since there are only 26 lowercase letters, for every pair we can:

Count the frequency of all characters in the first string. Count the frequency of all characters in the second string. Compare the frequencies of 'a' through 'z'. If any frequency difference is greater than 3, return "NO". Otherwise, return "YES".

Algorithm

For every corresponding pair (s[i], t[i]):

Create two frequency arrays of size 26. Count characters in s[i]. Count characters in t[i]. For every character from 'a' to 'z': Calculate the absolute difference between the two frequencies. If the difference is greater than 3, mark the pair as "NO". If all 26 characters satisfy the condition, mark the pair as "YES". Return the resulting array.

Python 3 Solution

def areSimilar(s, t):
    result = []

    for str1, str2 in zip(s, t):
        freq1 = [0] * 26
        freq2 = [0] * 26

        for ch in str1:
            freq1[ord(ch) - ord('a')] += 1

        for ch in str2:
            freq2[ord(ch) - ord('a')] += 1

        similar = True

        for i in range(26):
            if abs(freq1[i] - freq2[i]) > 3:
                similar = False
                break

        result.append("YES" if similar else "NO")

    return result

Complexity

Let L be the total length of the strings being processed.

For each pair, we count every character once and then check 26 letters.

Time Complexity:

O(L + 26n)

Since 26 is constant, this is effectively:

O(L)

Space Complexity:

O(26) = O(1) for the frequency arrays.

Why This Works

The definition of similarity depends only on character frequencies, not on the order of characters in the strings.

For example:

"abcabc" "cbacba"

have exactly the same frequency for every character, so they are similar.

The only thing we need to verify is:

|frequency_in_s - frequency_in_t| <= 3

for all 26 lowercase letters.

This problem was encountered in an IBM Coding Assessment.

If anyone else received a similar IBM assessment question, feel free to share the approach or any edge cases that should be considered.

#IBM #CodingAssessment #IBMJobs #DSA #Strings #FrequencyCounting #Python #CodingInterview #OnlineAssessment