2068. Check Whether Two Strings are Almost Equivalent

EasyHash TableStringCounting

Problem Description

The problem presents us with the concept of two strings, word1 and word2, being almost equivalent. Two strings are almost equivalent if for each letter in the alphabet, the number of times it appears in one word is within three of the number of times it appears in the other word. We are asked to write a function that takes two strings of equal length and returns true if they are almost equivalent, and false if they are not. This problem is essentially about comparing the frequency of each character from 'a' to 'z' in the two strings and checking if that frequency difference is at most 3.

Intuition

To solve this problem, the initial step is to understand that we need to count and compare the frequency of each letter in both strings. If the difference in the counts of any letter is more than 3, the strings are not almost equivalent.

The intuition behind the solution is to use a Counter data structure to store the frequencies of each letter from word1 and then decrement those frequencies based on the letters from word2. This way, we directly get the difference in frequencies between word1 and word2. By using the built-in Counter from Python's collections module, we can efficiently count the letter frequencies and easily compute the differences.

After processing both strings, we then check if all frequency differences are within the acceptable range (at most 3). The all() function is suitable for this check as it ensures that every letter satisfies the almost equivalent condition. If any letter's absolute frequency difference is greater than 3, all() immediately returns false, indicating that the words are not almost equivalent. Only if all frequency differences are within the allowed limit will all() return true, confirming that the strings are indeed almost equivalent.

The solution is concise, and the use of the Counter and absolutes of the differences streamlines the entire process from counting to comparison, making this a straightforward approach to solve the problem.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Solution Approach

In this solution, we're using the Counter data structure from Python's collections module, which is particularly useful for counting hashable objects (in this case, the characters of the strings). It internally maintains a dictionary where keys are the elements being counted and the values are their respective counts.

Here's a breakdown of the steps in the algorithm:

We initialize the Counter with word1. This gives us a dictionary where each key is a unique character from word1, and its corresponding value is the number of times the character appears in word1.
We iterate through each character c in word2 and decrement the count of c in our Counter by 1. If c wasn't in word1, its count in the Counter will be -1, accurately reflecting the difference in frequency between word1 and word2.
After processing both strings, our Counter now represents the net frequency differences of each character.
The final step is to examine if all values (net differences) in the Counter are less than or equal to 3 in absolute value. This is achieved by using the all() function combined with a generator expression. The expression abs(x) <= 3 is evaluated for every value x in the Counter. If they all satisfy this condition, it means that the frequency of no character differs by more than 3 between the strings, hence word1 and word2 are almost equivalent, and the function returns true. If even one such condition fails, the function returns false as the strings are not almost equivalent.

In terms of complexity:

The time complexity of the solution is O(N), where N is the length of the input strings. This is because we iterate over each string once.
The space complexity is O(1) despite using the Counter, as the size of the Counter is bounded by the number of unique characters in word1, which is at most 26 in the English alphabet. Hence, it is a constant space overhead.

This approach is efficient and exploits the constant upper bound on the number of unique characters. It elegantly simplifies the problem down to a single Counter check at the end.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Example Walkthrough

Let's consider word1 = "abc" and word2 = "bcd". We shall walk through the solution approach using these two words.

Step 1: Initialize the Counter with word1. This gives us a Counter object where each key is a character from word1, and the corresponding value is the frequency of that character in word1.

1Counter for word1: {'a': 1, 'b': 1, 'c': 1}

Step 2: Iterate through word2, decrementing the counts in the Counter by 1 for each character in word2.

After seeing 'b' in word2, decrement 'b' count by 1.

1Counter: {'a': 1, 'b': 0, 'c': 1}

After seeing 'c' in word2, decrement 'c' count by 1.

1Counter: {'a': 1, 'b': 0, 'c': 0}

After seeing 'd' in word2, since 'd' is not in the Counter, its count becomes -1.

1Counter: {'a': 1, 'b': 0, 'c': 0, 'd': -1}

Step 3: The Counter object now accurately reflects the difference in frequency for each character between word1 and word2.

Step 4: Use the all() function with a generator expression to verify that all frequency differences are within 3. We check if abs(x) <= 3 for every value x in the Counter.

For character 'a': abs(1) <= 3 is True.
For character 'b': abs(0) <= 3 is True.
For character 'c': abs(0) <= 3 is True.
For character 'd': abs(-1) <= 3 is True.

Since all conditions are True, all() returns True, hence word1 and word2 are almost equivalent and the function will return True.

This example clearly illustrates the solution approach – character counts are compared directly, and the process is both simple and efficient.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
5        # Create a counter object to count the frequency of each character in word1
6        char_counter = Counter(word1)
7      
8        # Decrement the count in the counter for each character in word2
9        for character in word2:
10            char_counter[character] -= 1
11          
12        # Check if the absolute difference of each character's frequency is at most 3
13        # If it is within [-3, 3] inclusive for every character, the words are almost equivalent
14        return all(abs(frequency) <= 3 for frequency in char_counter.values())
15
16# Example usage:
17# sol = Solution()
18# result = sol.checkAlmostEquivalent("abc", "pqr")
19# print(result)  # Output: True or False based on the words being almost equivalent
20

1class Solution {
2
3    // Function to check if two strings are almost equivalent
4    public boolean checkAlmostEquivalent(String word1, String word2) {
5        // Array to keep count of the frequency difference of each character
6        int[] charFrequencyDifference = new int[26];
7
8        // Increment the count for each character in word1
9        for (int i = 0; i < word1.length(); ++i) {
10            charFrequencyDifference[word1.charAt(i) - 'a']++;
11        }
12
13        // Decrement the count for each character in word2
14        for (int i = 0; i < word2.length(); ++i) {
15            charFrequencyDifference[word2.charAt(i) - 'a']--;
16        }
17
18        // Check if any character's frequency difference is greater than 3
19        for (int frequencyDifference : charFrequencyDifference) {
20            // If the absolute frequency difference is greater than 3, return false
21            if (Math.abs(frequencyDifference) > 3) {
22                return false;
23            }
24        }
25      
26        // If all characters' frequency differences are 3 or less, return true
27        return true;
28    }
29}
30

1class Solution {
2public:
3    // This function checks if two words are almost equivalent.
4    // Two words are almost equivalent if the absolute difference in the frequencies 
5    // of each letter in the words is at most 3.
6    bool checkAlmostEquivalent(string word1, string word2) {
7        int letterCounts[26] = {0}; // Initialize an array to count letters, one entry for each letter of the alphabet.
8
9        // Count the frequency of each letter in word1.
10        for (char& c : word1) {
11            ++letterCounts[c - 'a']; // Increment the count for this letter.
12        }
13
14        // Decrement the frequency count for each letter in word2.
15        for (char& c : word2) {
16            --letterCounts[c - 'a']; // Decrement the count for this letter.
17        }
18
19        // Check all the counters to ensure none of the frequencies' absolute differences are greater than 3.
20        for (int i = 0; i < 26; ++i) {
21            if (abs(letterCounts[i]) > 3) {
22                // If the absolute difference in frequencies of any letter is more than 3, words are not almost equivalent.
23                return false;
24            }
25        }
26
27        // If the function did not return false in the loop, the words are almost equivalent.
28        return true;
29    }
30};
31

1function checkAlmostEquivalent(word1: string, word2: string): boolean {
2    // Create an array of size 26 to represent each letter of the alphabet and initialize with 0
3    const letterCounts: number[] = new Array(26).fill(0);
4
5    // Iterate over each character in word1 and increment the count of the corresponding letter
6    for (const char of word1) {
7        letterCounts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
8    }
9
10    // Iterate over each character in word2 and decrement the count of the corresponding letter
11    for (const char of word2) {
12        letterCounts[char.charCodeAt(0) - 'a'.charCodeAt(0)]--;
13    }
14
15    // Check that the absolute difference in counts of each letter does not exceed 3
16    return letterCounts.every(count => Math.abs(count) <= 3);
17}
18

Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Time and Space Complexity

The time complexity of the given code is O(n) where n is the combined length of word1 and word2. This is because the algorithm goes through each character of word1 to build the counter and then iterates over all characters of word2 to adjust the counts. Each operation of increment or decrement in the counter takes constant time, hence the overall complexity remains linear with respect to the input size.

The space complexity is O(C) where C is the size of the character set used in the counter. Since the problem deals with lowercase English letters, C is at most 26. This is the space required to store the count of each character. Since C is a constant number, we can also consider the space complexity to be O(1), as it does not grow with the input size but is bounded by a fixed limit.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2068. Check Whether Two Strings are Almost Equivalent

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings