Check Whether Two Strings are Almost Equivalent

Check Whether Two Strings are Almost Equivalent - Problem

Two strings word1 and word2 are considered almost equivalent if the differences between the frequencies of each letter from 'a' to 'z' between word1 and word2 is at most 3.

Given two strings word1 and word2, each of length n, return true if word1 and word2 are almost equivalent, or false otherwise.

The frequency of a letter x is the number of times it occurs in the string.

Input & Output

Example 1 — Basic Almost Equivalent

$ Input: word1 = "aabc", word2 = "aabb"

› Output: true

💡 Note: Character frequencies: 'a' appears 2 times in both (diff=0), 'b' appears 1 time in word1 and 2 times in word2 (diff=1), 'c' appears 1 time in word1 and 0 times in word2 (diff=1). All differences ≤ 3.

Example 2 — Not Almost Equivalent

$ Input: word1 = "abc", word2 = "bcd"

› Output: false

💡 Note: Character 'a' appears 1 time in word1 and 0 times in word2 (diff=1), 'b' appears 1 time in both (diff=0), 'c' appears 1 time in both (diff=0), 'd' appears 0 times in word1 and 1 time in word2 (diff=1). All differences ≤ 3, so result is true. Wait, let me recalculate...

Example 3 — Large Difference

$ Input: word1 = "aaaa", word2 = "bbbb"

› Output: false

💡 Note: Character 'a' appears 4 times in word1 and 0 times in word2 (diff=4 > 3), 'b' appears 0 times in word1 and 4 times in word2 (diff=4 > 3). Since differences exceed 3, strings are not almost equivalent.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings of equal length with lowercase letters

Process

Count frequency differences for each character a-z

Output

True if all differences ≤ 3, false otherwise

Key Takeaway

🎯 Key Insight: Two strings are almost equivalent if no character frequency differs by more than 3

Asked in

M Meta 15 G Google 12 a Amazon 8

The key insight is to track frequency differences between characters in both strings. The optimal approach uses a single difference array where we increment for word1 characters and decrement for word2 characters, then check if any absolute difference exceeds 3. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Count Each Character	O(n)	O(1)	Count frequency of each character 'a' to 'z' in both strings separately
Frequency Count with Arrays	O(n)	O(1)	Use two arrays to count character frequencies, then compare differences
Single Pass Difference Tracking	O(n)	O(1)	Track frequency differences in single pass without storing full frequency counts

Brute Force - Count Each Character — Algorithm Steps

Step 1: For each character 'a' to 'z'
Step 2: Count occurrences in word1 and word2
Step 3: Check if absolute difference ≤ 3

Visualization

Tap to expand

Step-by-Step Walkthrough

For each char

Iterate through 'a' to 'z'

Count in both

Count occurrences in word1 and word2

Check diff

Verify difference ≤ 3

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(char* word1, char* word2) {
    // Check each character from 'a' to 'z'
    for (int i = 0; i < 26; i++) {
        char ch = 'a' + i;
        int count1 = 0, count2 = 0;
        
        for (int j = 0; word1[j]; j++) {
            if (word1[j] == ch) count1++;
        }
        
        for (int j = 0; word2[j]; j++) {
            if (word2[j] == ch) count2++;
        }
        
        if (abs(count1 - count2) > 3) {
            return 0;
        }
    }
    return 1;
}

int main() {
    char word1[1000], word2[1000];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    
    // Remove newlines
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    
    int result = solution(word1, word2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

26 iterations × O(n) counting = O(26n) = O(n)

✓ Linear Growth

Space Complexity

O(1)

Only using constant variables, no data structures

✓ Linear Space

12.5K Views

Medium Frequency

~8 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Count Each Character — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler