# String Range Queries to count number of distinct characters with updates

Given a string S of length N, and Q queries of the following type:

Type 1:1 i X

Update the i-th character of the string with the given character, X.

Type 2:L R

Count number of distinct characters in the given range [L, R].Constraint:

- 1<=N<=500000
- 1<=Q<20000
- |S|=N
- String S contains only lowercase alphabets.

**Examples:**

Input:S = “abcdbbd” Q = 6

2 3 6

1 5 z

2 1 1

1 4 a

1 7 d

2 1 7Output:

3

1

5Explanation:

For the Queries:

1. L = 3, R = 6

The different characters are:c, b, d.

ans = 3.

2. String after query updated as S=”abcdzbd”.

3. L = 1, R = 1

Only one different character.

and so on process all queries.

Input:S = “aaaaa”, Q = 2

1 2 b

2 1 4Output:

2

**Naive approach:**

**Query type 1:** Replace i-th character of the string with the given character.**Query type 2:** Traverse the string from L to R and count number of distinct characters.

**Time complexity:** O(N^{2})

**Efficient approach:** This approach is based on the Frequency-counting algorithm.

The idea is to use a HashMap to map distinct characters of the string with an Ordered_set which stores indices of its all occurrence. Ordered_set is used because it is based on Red-Black tree, so insertion and deletion of character will taken O ( log N ).

- Insert all characters of the string with its index into Hash-map
- For query of type 1, erase the occurrence of character at index i and insert occurrence of character X at index i in Hash-map
- For query of type 2, traverse all 26 characters and check if its occurrence is within the range [L, R], if yes then increment the count. After traversing print the value of count.

Below is the implementation of the above approach:

## C++

`#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `#include <ext/pb_ds/assoc_container.hpp>` `#include <ext/pb_ds/tree_policy.hpp>` `using` `namespace` `__gnu_pbds;` ` ` `#define ordered_set \` ` ` `tree<` `int` `, null_type, less<` `int` `>, \` ` ` `rb_tree_tag, \` ` ` `tree_order_statistics_node_update>` ` ` `// Function that returns the lower-` `// bound of the element in ordered_set` `int` `lower_bound(ordered_set set1, ` `int` `x)` `{` ` ` `// Finding the position of` ` ` `// the element` ` ` `int` `pos = set1.order_of_key(x);` ` ` ` ` `// If the element is not` ` ` `// present in the set` ` ` `if` `(pos == set1.size()) {` ` ` `return` `-1;` ` ` `}` ` ` ` ` `// Finding the element at` ` ` `// the position` ` ` `else` `{` ` ` `int` `element = *(set1.find_by_order(pos));` ` ` ` ` `return` `element;` ` ` `}` `}` ` ` `// Utility function to add the` `// position of all characters` `// of string into ordered set` `void` `insert(` ` ` `unordered_map<` `int` `, ordered_set>& hMap,` ` ` `string S, ` `int` `N)` `{` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `hMap[S[i] - ` `'a'` `].insert(i);` ` ` `}` `}` ` ` `// Utility function for update` `// the character at position P` `void` `Query1(` ` ` `string& S,` ` ` `unordered_map<` `int` `, ordered_set>& hMap,` ` ` `int` `pos, ` `char` `c)` `{` ` ` ` ` `// we delete the position of the` ` ` `// previous character as new` ` ` `// character is to be replaced` ` ` `// at the same position.` ` ` `pos--;` ` ` `int` `previous = S[pos] - ` `'a'` `;` ` ` `int` `current = c - ` `'a'` `;` ` ` `S[pos] = c;` ` ` `hMap[previous].erase(pos);` ` ` `hMap[current].insert(pos);` `}` ` ` `// Utility function to determine` `// number of different characters` `// in given range.` `void` `Query2(` ` ` `unordered_map<` `int` `, ordered_set>& hMap,` ` ` `int` `L, ` `int` `R)` `{` ` ` `// Iterate over all 26 alphabets` ` ` `// and check if it is in given` ` ` `// range using lower bound.` ` ` `int` `count = 0;` ` ` `L--;` ` ` `R--;` ` ` `for` `(` `int` `i = 0; i < 26; i++) {` ` ` `int` `temp = lower_bound(hMap[i], L);` ` ` `if` `(temp <= R and temp != -1)` ` ` `count++;` ` ` `}` ` ` `cout << count << endl;` `}` ` ` `// Driver code` `int` `main()` `{` ` ` `string S = ` `"abcdbbd"` `;` ` ` `int` `N = S.size();` ` ` ` ` `unordered_map<` `int` `, ordered_set> hMap;` ` ` ` ` `// Insert all characters with its` ` ` `// occurrence in the hash map` ` ` `insert(hMap, S, N);` ` ` ` ` `// Queries for sample input` ` ` `Query2(hMap, 3, 6);` ` ` `Query1(S, hMap, 5, ` `'z'` `);` ` ` `Query2(hMap, 1, 1);` ` ` `Query1(S, hMap, 4, ` `'a'` `);` ` ` `Query1(S, hMap, 7, ` `'d'` `);` ` ` `Query2(hMap, 1, 7);` ` ` ` ` `return` `0;` `}` |

**Output:**

3 1 5

Time complexity: **O(Q * logN)** where Q is number of queries and N is the size of the string.