Check Whether Two Strings are Almost Equivalent

Easy
1194.

Check Whether Two Strings are Almost Equivalent

Check Whether Two Strings are Almost Equivalent is an easy coding problem on strings, hash table and counting, asked in Amazon and Google interviews.

Two strings are almost equivalent when, for every letter from 'a' to 'z', the number of times it occurs in one string differs from the number of times it occurs in the other by at most 3.

Given two lowercase strings word1 and word2 of the same length, return true if they are almost equivalent and false otherwise.

Example 1

Input
word1 = "duel", word2 = "lead"
Output
true

Example 2

Input
word1 = "kkkkkiro", word2 = "kairoabc"
Output
false
Explanation
`k` occurs 5 times in `word1` but once in `word2` — a gap of 4.

Example 3

Input
word1 = "aaab", word2 = "bbbb"
Output
true
Explanation
`a` differs by 3 and `b` by 3, which is allowed.

Constraints

  • n == word1.length == word2.length
  • 1 <= n <= 100
  • word1 and word2 consist only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var checkAlmostEquivalent = function(word1, word2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check Whether Two Strings are Almost Equivalent — Solution

Check Whether Two Strings are Almost Equivalent solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check Whether Two Strings are Almost Equivalent is an easy coding problem on strings, hash table and counting, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Strings, Hash Table, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two strings are almost equivalent when, for every letter from 'a' to 'z', the number of times it occurs in one string differs from the number of times it occurs in the other by at most 3.

Given two lowercase strings word1 and word2 of the same length, return true if they are almost equivalent and false otherwise.

Example 1

Input: word1 = "duel", word2 = "lead"
Output: true

Example 2

Input: word1 = "kkkkkiro", word2 = "kairoabc"
Output: false
Explanation: `k` occurs 5 times in `word1` but once in `word2` — a gap of 4.

Example 3

Input: word1 = "aaab", word2 = "bbbb"
Output: true
Explanation: `a` differs by 3 and `b` by 3, which is allowed.

Constraints

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

Hints for Check Whether Two Strings are Almost Equivalent

  1. Hint 1

    Only letter counts matter, not positions.

  2. Hint 2

    Count the 26 letters of each word (or add for word1 and subtract for word2 in one array).

  3. Hint 3

    Check that every one of the 26 differences has absolute value at most 3.

How to solve Check Whether Two Strings are Almost Equivalent

Keep one array of 26 signed counters: add 1 for each letter of word1, subtract 1 for each letter of word2. Each counter is then the frequency difference of its letter.

Approach

  1. Initialise diff[26] = 0.
  2. For each character of word1, increment its counter; for each character of word2, decrement it.
  3. Return true exactly when every |diff[c]| <= 3.

Why it works

After both passes diff[c] = count1(c) - count2(c), which is precisely the quantity the definition bounds, and the check covers all 26 letters — including those absent from one or both words.

Complexity

  • Time — O(n + 26)
  • Space — O(1)

Pitfalls

  • Letters that appear in only one word must still be checked — iterate over all 26, not just one word's letters.
  • The bound is inclusive: a difference of exactly 3 is fine.
  • Use the absolute value; the gap may go either way.

Reference solution

Python

from collections import Counter

def checkAlmostEquivalent(word1: str, word2: str) -> bool:
    c1, c2 = Counter(word1), Counter(word2)
    return all(abs(c1[ch] - c2[ch]) <= 3 for ch in 'abcdefghijklmnopqrstuvwxyz')

Java

public static boolean checkAlmostEquivalent(String word1, String word2) {
    int[] diff = new int[26];
    for (int i = 0; i < word1.length(); i++) diff[word1.charAt(i) - 'a']++;
    for (int i = 0; i < word2.length(); i++) diff[word2.charAt(i) - 'a']--;
    for (int d : diff) if (Math.abs(d) > 3) return false;
    return true;
}

C++

bool checkAlmostEquivalent(string word1, string word2) {
    int diff[26] = {0};
    for (char c : word1) diff[c - 'a']++;
    for (char c : word2) diff[c - 'a']--;
    for (int d : diff) if (abs(d) > 3) return false;
    return true;
}

JavaScript

var checkAlmostEquivalent = function(word1, word2) {
    var diff = [];
    for (var z = 0; z < 26; z++) diff.push(0);
    for (var i = 0; i < word1.length; i++) diff[word1.charCodeAt(i) - 97]++;
    for (var j = 0; j < word2.length; j++) diff[word2.charCodeAt(j) - 97]--;
    for (var c = 0; c < 26; c++) if (Math.abs(diff[c]) > 3) return false;
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets