XORing String DSA Problem Solution

Posted by admin July 17, 2023
XORing String DSA Problem
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 consisting of lowercase Latin letters

(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 

    letter in the English Alphabet

Input

The first line of the input consists of a string

s

(1≤|s|≤106). The second line consists of a single integer

q

(1≤q≤106)

− the total number of queries. Then each of the next

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

  • 1 L R : (1≤L≤R≤|s|) 

  • 2 X Y : (1≤X≤|s|) 

    , (1≤Y≤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;
}