In this post, we are going to solve XORing String DSA Problem from Amazon’s 10th October Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.
XORing String DSA Problem Statement
You are given a string
consisting of lowercase Latin letters
. The score of a string is defined as the XOR of the frequencies of all the distinct letters in the string. You are required to handle two types of queries:
- 1 L R : Answer the score of the substring from L to R.
- 2 X Y : Update the character at the position X to the Y
letter in the English Alphabet
The first line of the input consists of a string
. The second line consists of a single integer
the total number of queries. Then each of the next
lines are queries of either of the following two types:
- 1 L R :
- 2 X Y :
,
For each query of type 1, you should output a single integer – the XOR of the frequencies of all distinct characters in that particular substring.
tti 4 2 3 1 1 1 2 2 1 2 1 2 3
2 0
XORing String DSA Problem Solution in C++
#include <bits/stdc++.h>
using namespace std;
struct fenwick {
vector<int> fen;
int n;
fenwick(int n) {
this->n = n + 1;
fen.assign(n + 1, 0);
}
void update(int x, int val) {
for (int i = x + 1; i < n; i += i & -i) {
fen[i] += val;
}
}
int query(int x) {
int res = 0;
for (int i = x + 1; i > 0; i -= i & -i) {
res += fen[i];
}
return res;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string s;
int q;
cin >> s >> q;
int n = s.size();
vector<fenwick> ds(26, fenwick(n));
for (int i = 0; i < n; ++i) {
ds[s[i] - 'a'].update(i, 1);
}
while (q--) {
int t, x, y;
cin >> t >> x >> y;
x--, y--;
if (t == 1) {
int ans = 0;
for (int i = 0; i < 26; ++i) {
ans ^= ds[i].query(x, y);
}
cout << ans << '\n';
} else {
ds[s[x] - 'a'].update(x, -1);
s[x] = (char)('a' + y);
ds[s[x] - 'a'].update(x, 1);
}
}
return 0;
}
1 thought on “XORing String DSA Problem Solution”