# XORing String DSA Problem Solution

XORing String DSA Problem

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

$s$$s$ consisting of lowercase Latin letters

$\left(a-z\right)$$(a-z)$. 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 ${}_{th}$

$_{th}$ letter in the English Alphabet

Input

The first line of the input consists of a string

$s$$s$

$\left(1\le |s|\le {10}^{6}\right)$$(1 \leq |s| \leq 10^6)$. The second line consists of a single integer

$q$$q$

$\left(1\le q\le {10}^{6}\right)$$(1 \leq q \leq 10^6)$

$-$$-$ the total number of queries. Then each of the next

$q$$q$ lines are queries of either of the following two types:

• 1 L R : $\left(1\le L\le R\le |s|\right)$

$(1 \leq L \leq R \leq |s|)$

• 2 X Y : $\left(1\le X\le |s|\right)$

$(1 \leq X \leq |s|)$ , $\left(1\le Y\le 26\right)$

$(1 \leq Y \leq 26)$

Output

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.

Example
Input
tti
4
2 3 1
1 1 2
2 1 2
1 2 3

Output
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;
}