Given a string S of length N, and M queries of the following type:
Type 1: 1 L x,
Indicates update Lth index of string S by character ‘x’.
Type 2: 2 L R str
Find the number of subsets in range L to R
which is equal to the string str modulo 1000000007.
Constraints :
|S| <= 100000,
M <= 100000,
1 <= L, R <= |S|,
|str| <= 26,
All characters in str are unique,
S & str consisting of lowercase latin letters.
Examples:
Input : N = 16, M = 3, S = “geeekkksgskeegks”
type = 2: L = 1, R = 7, str = “gek”
type = 1: index = 2, character = ‘x’
type = 2: L = 1, R = 7, str = “gek”
Output : 9 6 4
query2 : No of subsets in string S i range [1…7] that is equal to gek is 9.
query1 : string S is changed to gxeekkksgskeegks after second query.
query2 : No of subsets in string S i range [1…7] that is equal to gek is 6.
Naive Approach :
Query type 1: We will calculate the frequency of each character of the query string in the range [L…R] and then multiply all the calculated frequencies to get the desired result.
Query type 2: We will replace the i’th character of the string with the given character.
Time complexity : 0(m*n)
Efficient Approach :
- Using Segment Tree we can perform both operations in log(n) time. Every node of segment tree will contain frequency of characters in range [L..R].
- The function build takes n*log(n) time to create a segment tree with every node containing the frequency of characters of some segment of the string.
- The function get returns a vector containing frequency of all characters. Multiplication of all frequency of the given query string modulo 1e9+7 gives the desired result.
- The function update decreases the frequency of character placed earlier and increases the frequency of new character present in the nodes of the segment tree by one.
- The function add_two_result adds two vector and returns their result.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; #define N 400005 #define mod 1000000007 vector <int> seg_tree[N]; string str; // A recursive function that constructs // Segment Tree for given string void build(int pos, int st, int en) { if (st == en) { // Increment the frequency of character // by one if st is equal to en seg_tree[pos][str[st - 1] - 'a']++; return ; } int mid = st + en >> 1; // Build the segment tree for range st to mid build(2 * pos, st, mid); // Build the segment tree for range mid+1 to en build(2 * pos + 1, mid + 1, en); // It stores addition of frequency of // characters of both of its child after // segment tree is build for (int i = 0; i < 26; i++) seg_tree[pos][i] = seg_tree[2 * pos + 1][i] + seg_tree[2 * pos][i]; } // A utility function for // addition of two vectors vector <int> add_two_result(vector <int> v1, vector <int> v2) { vector <int> added_vec(26); // Adding two vector and storing // it in another vector for (int i = 0; i < 26; i++) added_vec[i] = v1[i] + v2[i]; // Returning final vector return added_vec; } // A recursive function that return vector // which contains frequency of every character vector <int> get(int pos, int l, int r, int st, int en) { // If segment of this node is // outside the given range if (l > en || r < st) { vector <int> empty(26, 0); return empty; } // If segment of this node is a part // of given range, then return the // frequency every character of the segment if (st >= l && en <= r) { return seg_tree[pos]; } // getting mid of st and en int mid = st + en >> 1; //storing answer of left child n v1 vector <int> v1 = get(2 * pos, l, r, st, mid); //storing answer of left child n v1 vector <int> v2 = get(2 * pos + 1, l, r, mid + 1, en); //returning the addition of both vectors return add_two_result(v1, v2); } // A recursive function that update // frequency of new and old character void update(int pos, int indx, int st, int en, char pre, char cur) { // If segment of this node is // outside the given range if (indx > en || indx < st) return; // Subtract frequency of previous character seg_tree[pos][pre - 'a']--; // Add frequency of new character seg_tree[pos][cur - 'a']++; if (st != en) { int mid = st + en >> 1; // update left child update(2 * pos, indx, st, mid, pre, cur); // update right child update(2 * pos + 1, indx, mid + 1, en, pre, cur); } } // Utility function to // initialize seg_tree vector void initialize() { for (int i = 0; i < N; i++) seg_tree[i].resize(26, 0); } int count_frequency(string s, vector <int> v) { int ans = 1; // multiplying frequency of all // characters in string hard for (int i = 0; s[i]; i++) ans = (ans * v[s[i] - 'a']) % mod; return ans; } // Driver Code int main() { int n, q, ans; vector <int> v; n = 15; str = "haardhhardrddrd"; //initialize and build the seg_tree vector initialize(); build(1, 1, n); string s = "hard"; // getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); // Calling count_frequency ans = count_frequency(s, v); cout << ans << '\n'; // Updating character at index 3 update(1, 3, 1, n, str[2], 'x'); str[2] = 'x'; // getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); //calling count_frequency ans = count_frequency(s, v); cout << ans << '\n'; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { final static int N = 400005; final static int mod = 1000000007; static int[][] seg_tree = new int[N][26]; static StringBuilder str; // A recursive function that constructs // Segment Tree for given String static void build(int pos, int st, int en) { if (st == en) { // Increment the frequency of character // by one if st is equal to en seg_tree[pos][str.charAt(st - 1) - 'a']++; return; } int mid = st + en >> 1; // Build the segment tree for range st to mid build(2 * pos, st, mid); // Build the segment tree for range mid+1 to en build(2 * pos + 1, mid + 1, en); // It stores addition of frequency of // characters of both of its child after // segment tree is build for (int i = 0; i < 26; i++) seg_tree[pos][i] = seg_tree[2 * pos + 1][i] + seg_tree[2 * pos][i]; } // A utility function for // addition of two vectors static int[] add_two_result(int[] v1, int[] v2) { int[] added_vec = new int[26]; // Adding two vector and storing // it in another vector for (int i = 0; i < 26; i++) added_vec[i] = v1[i] + v2[i]; // Returning final vector return added_vec; } // A recursive function that return vector // which contains frequency of every character static int[] get(int pos, int l, int r, int st, int en) { // If segment of this node is // outside the given range if (l > en || r < st) { int[] empty = new int[26]; return empty; } // If segment of this node is a part // of given range, then return the // frequency every character of the segment if (st >= l && en <= r) { return seg_tree[pos]; } // getting mid of st and en int mid = st + en >> 1; // storing answer of left child n v1 int[] v1 = get(2 * pos, l, r, st, mid); // storing answer of left child n v1 int[] v2 = get(2 * pos + 1, l, r, mid + 1, en); // returning the addition of both vectors return add_two_result(v1, v2); } // A recursive function that update // frequency of new and old character static void update(int pos, int indx, int st, int en, char pre, char cur) { // If segment of this node is // outside the given range if (indx > en || indx < st) return; // Subtract frequency of previous character seg_tree[pos][pre - 'a']--; // Add frequency of new character seg_tree[pos][cur - 'a']++; if (st != en) { int mid = st + en >> 1; // update left child update(2 * pos, indx, st, mid, pre, cur); // update right child update(2 * pos + 1, indx, mid + 1, en, pre, cur); } } static int count_frequency(String s, int[] v) { int ans = 1; // multiplying frequency of all // characters in String hard for (int i = 0; i < s.length(); i++) ans = (ans * v[s.charAt(i) - 'a']) % mod; return ans; } // Driver Code public static void main(String[] args) { int n, q, ans; int[] v; n = 15; str = new StringBuilder("haardhhardrddrd"); build(1, 1, n); String s = "hard"; // getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); // Calling count_frequency ans = count_frequency(s, v); System.out.println(ans); // Updating character at index 3 update(1, 3, 1, n, str.charAt(2), 'x'); str.setCharAt(2, 'x'); // getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); // calling count_frequency ans = count_frequency(s, v); System.out.println(ans); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 implementation of the approach N = 400005mod = 1000000007 seg_tree = [[0 for i in range(26)] for i in range(N)] str = "" # A recursive function that constructs # Segment Tree for given def build(pos, st, en): if (st == en): # Increment the frequency of character # by one if st is equal to en seg_tree[pos][ord(str[st - 1] )- ord('a')]+=1 return mid = st + en >> 1 # Build the segment tree for range st to mid build(2 * pos, st, mid) # Build the segment tree for range mid+1 to en build(2 * pos + 1, mid + 1, en) # It stores addition of frequency of # characters of both of its child after # segment tree is build for i in range(26): seg_tree[pos][i] = seg_tree[2 * pos + 1][i] + \ seg_tree[2 * pos][i] # A utility function for # addition of two vectors def add_two_result(v1,v2): added_vec=[0]*(26) # Adding two vector and storing # it in another vector for i in range(26): added_vec[i] = v1[i] + v2[i] # Returning final vector return added_vec # A recursive function that return vector # which contains frequency of every character def get(pos, l, r,st, en): # If segment of this node is # outside the given range if (l > en or r < st): empty = [0]*26 return empty # If segment of this node is a part # of given range, then return the # frequency every character of the segment if (st >= l and en <= r): return seg_tree[pos] # getting mid of st and en mid = st + en >> 1 # storing answer of left child n v1 v1 = get(2 * pos, l,r, st, mid) # storing answer of left child n v1 v2 = get(2 * pos + 1,l, r, mid + 1, en) # returning the addition of both vectors return add_two_result(v1, v2) # A recursive function that update # frequency of new and old character def update(pos, indx, st,en,pre,cur): # If segment of this node is # outside the given range if (indx > en or indx < st): return # Subtract frequency of previous character seg_tree[pos][ord(pre) - ord('a')]-=1 # Add frequency of new character seg_tree[pos][ord(cur) - ord('a')]+=1 if (st != en): mid = st + en >> 1 # update left child update(2 * pos,indx, st,mid, pre, cur) # update right child update(2 * pos + 1, indx,mid + 1, en, pre, cur) def count_frequency(s,v): ans = 1 # multiplying frequency of all # characters in hard i = 0 while i < len(s): ans = (ans * v[ord(s[i]) - ord('a')]) % mod i += 1 return ans # Driver Code if __name__ == '__main__': v=[] n = 15 str = "haardhhardrddrd" str=[i for i in str] build(1, 1, n) s = "hard" # getting frequency of all # characters from 1 to 5 v = get(1, 1, 5, 1, n) # Calling count_frequency ans = count_frequency(s, v) print(ans) # Updating character at index 3 update(1, 3, 1, n, str[2], 'x') str[2] = 'x' # getting frequency of all # characters from 1 to 5 v = get(1, 1, 5, 1, n) # calling count_frequency ans = count_frequency(s, v) print(ans) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System; using System.Text; class GFG{ readonly static int N = 400005; readonly static int mod = 1000000007; static int[,] seg_tree = new int[N, 26]; static StringBuilder str; // A recursive function that constructs // Segment Tree for given String static void build(int pos, int st, int en) { if (st == en) { // Increment the frequency of character // by one if st is equal to en seg_tree[pos,str[st - 1] - 'a']++; return; } int mid = st + en >> 1; // Build the segment tree for range st to mid build(2 * pos, st, mid); // Build the segment tree for range mid+1 to en build(2 * pos + 1, mid + 1, en); // It stores addition of frequency of // characters of both of its child after // segment tree is build for(int i = 0; i < 26; i++) seg_tree[pos, i] = seg_tree[2 * pos + 1, i] + seg_tree[2 * pos, i]; } // A utility function for // addition of two vectors static int[] add_two_result(int[] v1, int[] v2) { int[] added_vec = new int[26]; // Adding two vector and storing // it in another vector for(int i = 0; i < 26; i++) added_vec[i] = v1[i] + v2[i]; // Returning readonly vector return added_vec; } // A recursive function that return vector // which contains frequency of every character static int[] get(int pos, int l, int r, int st, int en) { // If segment of this node is // outside the given range if (l > en || r < st) { int[] empty = new int[26]; return empty; } // If segment of this node is a part // of given range, then return the // frequency every character of the segment if (st >= l && en <= r) { return GetRow(seg_tree, pos); } // Getting mid of st and en int mid = st + en >> 1; // Storing answer of left child n v1 int[] v1 = get(2 * pos, l, r, st, mid); // Storing answer of left child n v1 int[] v2 = get(2 * pos + 1, l, r, mid + 1, en); // Returning the addition of both vectors return add_two_result(v1, v2); } // A recursive function that update // frequency of new and old character static void update(int pos, int indx, int st, int en, char pre, char cur) { // If segment of this node is // outside the given range if (indx > en || indx < st) return; // Subtract frequency of previous character seg_tree[pos,pre - 'a']--; // Add frequency of new character seg_tree[pos,cur - 'a']++; if (st != en) { int mid = st + en >> 1; // update left child update(2 * pos, indx, st, mid, pre, cur); // update right child update(2 * pos + 1, indx, mid + 1, en, pre, cur); } } static int count_frequency(String s, int[] v) { int ans = 1; // Multiplying frequency of all // characters in String hard for(int i = 0; i < s.Length; i++) ans = (ans * v[s[i] - 'a']) % mod; return ans; } public static int[] GetRow(int[,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for(var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } // Driver Code public static void Main(String[] args) { int n, ans; int[] v; n = 15; str = new StringBuilder("haardhhardrddrd"); build(1, 1, n); String s = "hard"; // Getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); // Calling count_frequency ans = count_frequency(s, v); Console.WriteLine(ans); // Updating character at index 3 update(1, 3, 1, n, str[2], 'x'); str[2] = 'x'; // Getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); // Calling count_frequency ans = count_frequency(s, v); Console.WriteLine(ans); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript implementation of the approach var N = 400005; var mod = 1000000007; var seg_tree = Array.from(Array(N), ()=>Array(26).fill(0)); var str = ""; // A recursive function that constructs // Segment Tree for given String function build(pos, st, en) { if (st == en) { // Increment the frequency of character // by one if st is equal to en seg_tree[pos][str[st - 1].charCodeAt(0) - 'a'.charCodeAt(0)]++; return; } var mid = st + en >> 1; // Build the segment tree for range st to mid build(2 * pos, st, mid); // Build the segment tree for range mid+1 to en build(2 * pos + 1, mid + 1, en); // It stores addition of frequency of // characters of both of its child after // segment tree is build for(var i = 0; i < 26; i++) seg_tree[pos][ i] = seg_tree[2 * pos + 1][ i] + seg_tree[2 * pos][ i]; } // A utility function for // addition of two vectors function add_two_result(v1, v2) { var added_vec = Array(26).fill(0); // Adding two vector and storing // it in another vector for(var i = 0; i < 26; i++) added_vec[i] = v1[i] + v2[i]; // Returning readonly vector return added_vec; } // A recursive function that return vector // which contains frequency of every character function get(pos, l, r, st, en) { // If segment of this node is // outside the given range if (l > en || r < st) { var empty = Array(26).fill(0); return empty; } // If segment of this node is a part // of given range, then return the // frequency every character of the segment if (st >= l && en <= r) { return GetRow(seg_tree, pos); } // Getting mid of st and en var mid = st + en >> 1; // Storing answer of left child n v1 var v1 = get(2 * pos, l, r, st, mid); // Storing answer of left child n v1 var v2 = get(2 * pos + 1, l, r, mid + 1, en); // Returning the addition of both vectors return add_two_result(v1, v2); } // A recursive function that update // frequency of new and old character function update(pos, indx, st, en, pre, cur) { // If segment of this node is // outside the given range if (indx > en || indx < st) return; // Subtract frequency of previous character seg_tree[pos][pre.charCodeAt(0) - 'a'.charCodeAt(0)]--; // Add frequency of new character seg_tree[pos][cur.charCodeAt(0) - 'a'.charCodeAt(0)]++; if (st != en) { var mid = st + en >> 1; // update left child update(2 * pos, indx, st, mid, pre, cur); // update right child update(2 * pos + 1, indx, mid + 1, en, pre, cur); } } function count_frequency(s, v) { var ans = 1; // Multiplying frequency of all // characters in String hard for(var i = 0; i < s.length; i++) ans = (ans * v[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]) % mod; return ans; } function GetRow(matrix, row) { var rowLength = matrix[0].length; var rowVector = Array(rowLength).fill(0); for(var i = 0; i < rowLength; i++) rowVector[i] = matrix[row][i]; return rowVector; } // Driver Code var n, ans; var v = []; n = 15; str = "haardhhardrddrd".split(''); build(1, 1, n); var s = "hard"; // Getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); // Calling count_frequency ans = count_frequency(s, v); document.write(ans+"<br>"); // Updating character at index 3 update(1, 3, 1, n, str[2], 'x'); str[2] = 'x'; // Getting frequency of all // characters from 1 to 5 v = get(1, 1, 5, 1, n); // Calling count_frequency ans = count_frequency(s, v); document.write(ans); // This code is contributed by rrrtnx. </script> |
Output
2 1
Time complexity : 0(m*log(n)+n*log(n))
Auxiliary Space: O(n)
Related Topic: Segment Tree
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
