2068. Check Whether Two Strings are Almost Equivalent
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.
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
withword1
. This gives us a dictionary where each key is a unique character fromword1
, and its corresponding value is the number of times the character appears inword1
. -
We iterate through each character
c
inword2
and decrement the count ofc
in ourCounter
by 1. Ifc
wasn't inword1
, its count in theCounter
will be-1
, accurately reflecting the difference in frequency betweenword1
andword2
. -
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 theall()
function combined with a generator expression. The expressionabs(x) <= 3
is evaluated for every valuex
in theCounter
. If they all satisfy this condition, it means that the frequency of no character differs by more than 3 between the strings, henceword1
andword2
are almost equivalent, and the function returnstrue
. If even one such condition fails, the function returnsfalse
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 theCounter
is bounded by the number of unique characters inword1
, 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
.
Counter 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.
Counter: {'a': 1, 'b': 0, 'c': 1}
- After seeing 'c' in
word2
, decrement 'c' count by 1.
Counter: {'a': 1, 'b': 0, 'c': 0}
- After seeing 'd' in
word2
, since 'd' is not in theCounter
, its count becomes-1
.
Counter: {'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
isTrue
. - For character 'b':
abs(0) <= 3
isTrue
. - For character 'c':
abs(0) <= 3
isTrue
. - For character 'd':
abs(-1) <= 3
isTrue
.
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
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!