Two strings word1 and word2 are considered almost equivalent if the differences between the frequencies of each letter from 'a' to 'z' between word1 and word2 is at most 3.
Given two strings word1 and word2, each of length n, return true if word1 and word2 are almost equivalent, or false otherwise.
The frequency of a letter x is the number of times it occurs in the string.
Example 1:
Input: word1 = "aaaa ", word2 = "bccb " Output: false Explanation: There are 4 'a's in "aaaa " but 0 'a's in "bccb ". The difference is 4, which is more than the allowed 3.
Example 2:
Input: word1 = "abcdeef ", word2 = "abaaacc " Output: true Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3: - 'a' appears 1 time in word1 and 4 times in word2. The difference is 3. - 'b' appears 1 time in word1 and 1 time in word2. The difference is 0. - 'c' appears 1 time in word1 and 2 times in word2. The difference is 1. - 'd' appears 1 time in word1 and 0 times in word2. The difference is 1. - 'e' appears 2 times in word1 and 0 times in word2. The difference is 2. - 'f' appears 1 time in word1 and 0 times in word2. The difference is 1.
Example 3:
Input: word1 = "cccddabba ", word2 = "babababab " Output: true Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3: - 'a' appears 2 times in word1 and 4 times in word2. The difference is 2. - 'b' appears 2 times in word1 and 5 times in word2. The difference is 3. - 'c' appears 3 times in word1 and 0 times in word2. The difference is 3. - 'd' appears 2 times in word1 and 0 times in word2. The difference is 2.
Constraints:
n == word1.length == word2.length1 <= n <= 100word1 and word2 consist only of lowercase English letters.program almost_equivalent_strings
implicit none
character(len=:), allocatable :: word1, word2
integer :: n
logical :: result
! Example 1
n = 6
allocate(character(len=n) :: word1, word2)
word1 = "aaaa "
word2 = "bccb "
result = almost_equivalent(word1, word2)
print *, result
! Example 2
n = 9
allocate(character(len=n) :: word1, word2)
word1 = "abcdeef "
word2 = "abaaacc "
result = almost_equivalent(word1, word2)
print *, result
! Example 3
n = 11
allocate(character(len=n) :: word1, word2)
word1 = "cccddabba "
word2 = "babababab "
result = almost_equivalent(word1, word2)
print *, result
contains
function almost_equivalent(word1, word2) result(result)
implicit none
character(len=*), intent(in) :: word1, word2
integer :: i, j, count
logical :: result
result = .false.
do i = 97, 122 ! 'a' to 'z'
count = 0
do j = 1, len(word1)
if (word1(j:j) == char(i)) then
count = count + 1
end if
end do
do j = 1, len(word2)
if (word2(j:j) == char(i)) then
count = count - 1
end if
end do
if (abs(count) > 3) then
exit
end if
end do
result = abs(count) <= 3
end function almost_equivalent
end program almost_equivalent_stringsF
At line 18 of file temp.f95 Fortran runtime error: Attempting to allocate already allocated variable 'word1' Error termination. Backtrace: #0 0x7ccb9829a960 in ??? #1 0x7ccb9829b4d9 in ??? #2 0x57cd15d3d5fb in MAIN__ #3 0x57cd15d3db68 in main
program almost_equivalent_strings
implicit none
integer, parameter :: MAX_LETTERS = 26
integer :: n, i, j
character(len=100) :: word1, word2
integer :: letter_freqs(MAX_LETTERS)
integer :: diff_freqs(MAX_LETTERS)
! Read the input
read(*,*) n
read(*,*) word1
read(*,*) word2
! Initialize the letter frequencies
letter_freqs = 0
do i = 1, n
letter_freqs(ichar(word1(i:i)) - ichar('a') + 1) = letter_freqs(ichar(word1(i:i)) - ichar('a') + 1) + 1
letter_freqs(ichar(word2(i:i)) - ichar('a') + 1) = letter_freqs(ichar(word2(i:i)) - ichar('a') + 1) + 1
end do
! Calculate the differences between the frequencies
diff_freqs = abs(letter_freqs - transpose(letter_freqs))
! Check if the differences are at most 3
if (any(diff_freqs > 3)) then
write(*,*) "false"
else
write(*,*) "true"
end if
end program almost_equivalent_strings
temp.f95:23:48:
23 | diff_freqs = abs(letter_freqs - transpose(letter_freqs))
| 1
Error: ‘matrix’ argument of ‘transpose’ intrinsic at (1) must be of rank 2
import collections
def maxGeneticDifference(parents, queries):
M = 17
tr = [0, 0]
def insert(x):
nonlocal tr
u = 0
for i in range(M - 1, -1, -1):
v = (x >> i) & 1
if not tr[u][v]:
tr[u][v] = len(tr)
tr.append([0, 0])
u = tr[u][v]
def query(x, y=0):
u = 0
ans = 0
for i in range(M - 1, -1, -1):
v = ((x >> i) & 1) ^ 1
if not tr[u][v]:
v ^= 1
ans |= (y := (y << 1) | v)
u = tr[u][v]
return ans
def dfs(u, tree=0, g=collections.defaultdict(list), ans=None):
nonlocal tr
insert(tree := tree ^ u)
ans[u] = query(tree)
for v in g[u]:
dfs(v, tree, g, ans)
n = len(parents)
root = -1
graph = collections.defaultdict(list)
for i, parent in enumerate(parents):
if parent != -1:
graph[parent].append(i)
else:
root = i
ans = [0] * n
dfs(root, 0, graph, ans)
result = [ans[node] ^ val for node, val in queries]
return result
1. Initialize a trie as the data structure for holding our bitwise XOR results.
insert, query, and dfs.insert, add numbers to the trie. Each bit of the number represents the node connected to the root node.query, find the maximum genetic difference in the trie given a genetic value.dfs, traverse the tree and perform the query function for every node while inserting its genetic value.parents array.dfs function for the root node to populate the trie.queries and XOR the gene value with the result from the trie to find the maximum genetic difference.#include <vector>
#include <bitset>
using namespace std;
const int M = 17;
vector<int> tr[1 << M];
void insert(int x) {
int u = 0;
for (int i = M - 1; i >= 0; --i) {
int v = (x >> i) & 1;
if (!tr[u][v]) tr[u][v] = tr.size(), tr.emplace_back(2);
u = tr[u][v];
}
}
int query(int x, int y = 0) {
int u = 0, ans = 0;
for (int i = M - 1; i >= 0; --i) {
int v = ((x >> i) & 1) ^ 1;
if (!tr[u][v]) v ^= 1;
ans |= (y = (y << 1) | v);
u = tr[u][v];
}
return ans;
}
void dfs(int u, int tree = 0, vector<vector<int>>& g = {}, vector<int>& ans = {}) {
insert(tree ^= u);
ans[u] = query(tree);
for (int v : g[u]) dfs(v, tree, g, ans);
}
vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
int n = parents.size();
vector<vector<int>> edges(n);
int root;
for (int i = 0; i < n; ++i) {
if (parents[i] == -1) {
root = i;
} else {
edges[parents[i]].push_back(i);
}
}
vector<int> ans(n);
dfs(root, 0, edges, ans);
vector<int> result(queries.size());
for (int i = 0; i < queries.size(); ++i) {
result[i] = ans[queries[i][0]] ^ queries[i][1];
}
return result;
}
1. Initialize a trie as the data structure for holding our bitwise XOR results.
insert, query, and dfs.insert, add numbers to the trie. Each bit of the number represents the node connected to the root node.query, find the maximum genetic difference in the trie given a genetic value.dfs, traverse the tree and perform the query function for every node while inserting its genetic value.parents array.dfs function for the root node to populate the trie.queries and XOR the gene value with the result from the trie to find the maximum genetic difference.