Sponsored
Sponsored
This approach utilizes arrays to count the frequency of each letter from 'a' to 'z' for both strings. By iterating through the characters of each word, we can populate two frequency arrays. Then, by comparing the absolute differences between corresponding elements of these arrays, we can determine if the words are almost equivalent.
Time Complexity: O(n + 26), which simplifies to O(n) where n is the length of the words.
Space Complexity: O(1) since the frequency arrays have a constant size of 26.
1def are_almost_equivalent(word1, word2):
2 freq1 = [0] * 26
3 freq2 = [0] * 26
4
5 for ch1, ch2 in zip(word1, word2):
6 freq1[ord(ch1) - ord('a')] += 1
7 freq2[ord(ch2) - ord('a')] += 1
8
9 return all(abs(f1 - f2) <= 3 for f1, f2 in zip(freq1, freq2))
10
11word1 = "abcdeef"
12word2 = "abaaacc"
13print(are_almost_equivalent(word1, word2))The Python solution utilizes lists to count letter frequencies, zipped with characters from each word. The method checks whether the maximum frequency difference does not exceed 3.
This alternate approach uses the hashmap or hash table data structure to record character frequencies for both strings. Hash maps are dynamic, allowing insertion without specifying a fixed field size. The hash maps' keys are characters, and their values are frequencies. The function calculates differences between frequency keys of two maps.
Time Complexity: O(n), limited by character frequency computation.
Space Complexity: O(1), determined by number of distinct characters, since max 26 distinct alphabets.
1import java.
In this Java code, the HashMap is applied for flexible frequency entries. It sets frequency values of each letter in both words by defaulting to zero, modifying only occurring characters. The letter comparison ensures no character's frequency difference exceeds 3.