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.
1#include <stdio.h>
2#include <stdbool.h>
3#include <string.h>
4#include <stdlib.h>
5
6bool areAlmostEquivalent(char *word1, char *word2) {
7 int freq1[26] = {0};
8 int freq2[26] = {0};
9
10 int n = strlen(word1);
11 for (int i = 0; i < n; i++) {
12 freq1[word1[i] - 'a']++;
13 freq2[word2[i] - 'a']++;
14 }
15
16 for (int i = 0; i < 26; i++) {
17 if (abs(freq1[i] - freq2[i]) > 3) {
18 return false;
19 }
20 }
21 return true;
22}
23
24int main() {
25 char *word1 = "abcdeef";
26 char *word2 = "abaaacc";
27 printf("%s\n", areAlmostEquivalent(word1, word2) ? "true" : "false");
28 return 0;
29}The function areAlmostEquivalent initializes two integer arrays of size 26 to zero, representing the frequencies of each character. It iterates through the characters of the input strings to populate these frequency arrays. Finally, it checks that the absolute difference for any character's frequency does not exceed 3, returning false if it does, and true otherwise.
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.
1#include <iostream>
2#include <unordered_map>
#include <string>
#include <cmath>
using namespace std;
bool areAlmostEquivalent(string word1, string word2) {
unordered_map<char, int> freq1, freq2;
for (char ch : word1) freq1[ch]++;
for (char ch : word2) freq2[ch]++;
for (char ch = 'a'; ch <= 'z'; ch++) {
if (abs(freq1[ch] - freq2[ch]) > 3) {
return false;
}
}
return true;
}
int main() {
cout << areAlmostEquivalent("abcdeef", "abaaacc") << endl; // Output: 1 (true)
return 0;
}The C++ code uses unordered_map containers to store character frequencies. The frequency difference analysis is done by iterating through alphabetical characters, ensuring deviations do not surpass 3.