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 7 Output: 3 1 5 Explanation: 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 4 Output: 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 the number of distinct characters.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number // of distinct characters in // the range [L, R] void Query2(string S, int L, int R) { int cnt = 0; for ( int i = L - 1; i < R; i++) { bool found = false ; for ( int j = L - 1; j < i; j++) { if (S[i] == S[j]) { found = true ; break ; } } if (!found) cnt++; } cout << cnt << endl; } // Function to update the i-th // character of the string // with the given character X void Query1(string& S, int i, char X) { S[i - 1] = X; } // Driver code int main() { string S = "abcdbbd" ; int N = S.size(); // Queries for sample input Query2(S, 3, 6); Query1(S, 5, 'z' ); Query2(S, 1, 1); Query1(S, 4, 'a' ); Query1(S, 7, 'd' ); Query2(S, 1, 7); return 0; } |
Java
import java.util.HashSet; class Main { // Function to count the number // of distinct characters in // the range [L, R] static void Query2(String S, int L, int R) { int cnt = 0 ; for ( int i = L - 1 ; i < R; i++) { boolean found = false ; for ( int j = L - 1 ; j < i; j++) { if (S.charAt(i) == S.charAt(j)) { found = true ; break ; } } if (!found) cnt++; } System.out.println(cnt); } // Function to update the i-th // character of the string // with the given character X static void Query1(StringBuilder S, int i, char X) { S.setCharAt(i - 1 , X); } // Driver code public static void main(String[] args) { StringBuilder S = new StringBuilder( "abcdbbd" ); int N = S.length(); Query2(S.toString(), 3 , 6 ); Query1(S, 5 , 'z' ); Query2(S.toString(), 1 , 1 ); Query1(S, 4 , 'a' ); Query1(S, 7 , 'd' ); Query2(S.toString(), 1 , 7 ); } } |
Python3
# Function to count the number # of distinct characters in # the range [L, R] def Query2(S, L, R): cnt = 0 for i in range (L - 1 , R): found = False for j in range (L - 1 , i): if S[i] = = S[j]: found = True break if not found: cnt + = 1 print (cnt) # Function to update the i-th # character of the string # with the given character X def Query1(S, i, X): S[i - 1 ] = X # Driver code if __name__ = = "__main__" : S = list ( "abcdbbd" ) N = len (S) # Queries for sample input Query2(S, 3 , 6 ) Query1(S, 5 , 'z' ) Query2(S, 1 , 1 ) Query1(S, 4 , 'a' ) Query1(S, 7 , 'd' ) Query2(S, 1 , 7 ) |
C#
using System; class Program { // Function to count the number of distinct characters in the range [L, R] static void Query2( string S, int L, int R) { int cnt = 0; for ( int i = L - 1; i < R; i++) { bool found = false ; for ( int j = L - 1; j < i; j++) { if (S[i] == S[j]) { found = true ; break ; } } if (!found) cnt++; } Console.WriteLine(cnt); } // Function to update the i-th character of the string with the given character X static void Query1( ref string S, int i, char X) { // In C#, strings are immutable, so you need to use a StringBuilder // to modify a character at a specific index. var sb = new System.Text.StringBuilder(S); sb[i - 1] = X; S = sb.ToString(); } // Driver code static void Main( string [] args) { string S = "abcdbbd" ; int N = S.Length; // Queries for sample input Query2(S, 3, 6); Query1( ref S, 5, 'z' ); Query2(S, 1, 1); Query1( ref S, 4, 'a' ); Query1( ref S, 7, 'd' ); Query2(S, 1, 7); } } |
Javascript
<script> //JavaScript program for the above approach // Function to count the number // of distinct characters in // the range [L, R] function Query2(S, L, R) { let cnt = 0; for (let i = L - 1; i < R; i++) { let found = false ; for (let j = L - 1; j < i; j++) { if (S[i] === S[j]) { found = true ; break ; } } if (!found) cnt++; } document.write(cnt+ "<br>" ); } // Function to update the i-th // character of the string // with the given character X function Query1(S, i, X) { S = S.split( '' ); S[i - 1] = X; S = S.join( '' ); return S; } let S = "abcdbbd" ; let N = S.length; // Queries for sample input Query2(S, 3, 6); S = Query1(S, 5, 'z' ); Query2(S, 1, 1); S = Query1(S, 4, 'a' ); S = Query1(S, 7, 'd' ); Query2(S, 1, 7); // This code is contributed by Susobhan Akhuli </script> |
3 1 5
Time complexity: O(N2)
Space complexity: O(1)
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; } |
Java
import java.util.*; import java.util.stream.*; public class Main { public static void main(String[] args) { String S = "abcdbbd" ; int N = S.length(); Map<Integer, TreeSet<Integer>> hMap = new HashMap<>(); // 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 ); } // Utility function to add the // position of all characters // of string into TreeSet public static void insert(Map<Integer, TreeSet<Integer>> hMap, String S, int N) { for ( int i = 0 ; i < N; i++) { int c = S.charAt(i) - 'a' ; if (!hMap.containsKey(c)) { hMap.put(c, new TreeSet<>()); } hMap.get(c).add(i); } } // Utility function for update // the character at position P public static void query1(String S, Map<Integer, TreeSet<Integer>> 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.charAt(pos) - 'a' ; int current = c - 'a' ; char [] chars = S.toCharArray(); chars[pos] = c; S = String.valueOf(chars); hMap.get(previous).remove(pos); if (!hMap.containsKey(current)) { hMap.put(current, new TreeSet<>()); } hMap.get(current).add(pos); } // Utility function to determine // number of different characters // in given range. public static void query2(Map<Integer, TreeSet<Integer>> hMap, int L, int R) { // Iterate over all 26 alphabets // and check if it is in given // range using floor() method. int count = 0 ; L--; R--; for ( int i = 0 ; i < 26 ; i++) { if (hMap.containsKey(i)) { Integer temp = hMap.get(i).floor(R); if (temp != null && temp >= L) { count++; } } } System.out.println(count); } } |
Python3
# Python equivalent of the above java code import collections # Insert all characters with its # occurrence in the hash map def insert(hMap, S, N): for i in range (N): c = ord (S[i]) - ord ( 'a' ) if c not in hMap: hMap = [] hMap.append(i) # Utility function for update # the character at position P def query1(S, hMap, pos, c): # We delete the position of the # previous character as new # character is to be replaced # at the same position. pos - = 1 previous = ord (S[pos]) - ord ( 'a' ) current = ord (c) - ord ( 'a' ) S = S[:pos] + c + S[pos + 1 :] hMap[previous].remove(pos) if current not in hMap: hMap[current] = [] hMap[current].append(pos) # Utility function to determine # number of different characters # in given range. def query2(hMap, L, R): # Iterate over all 26 alphabets # and check if it is in given # range using floor() method. count = 0 L - = 1 R - = 1 for i in range ( 26 ): if i in hMap.keys(): temp = list ( filter ( lambda x: x< = R and x> = L, hMap[i])) if len (temp): count + = 1 print (count) if __name__ = = "__main__" : S = "abcdbbd" N = len (S) hMap = collections.defaultdict( list ) 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 ) |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { public static void Main() { string S = "abcdbbd" ; int N = S.Length; Dictionary< int , List< int >> hMap = new Dictionary< int , List< int >>(); 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); } // Insert all characters with its occurrence in the hash map public static void Insert(Dictionary< int , List< int >> hMap, string S, int N) { for ( int i = 0; i < N; i++) { int c = S[i] - 'a' ; if (!hMap.ContainsKey(c)) { hMap = new List< int >(); } hMap.Add(i); } } // Utility function for update the character at position P public static void Query1( string S, Dictionary< int , List< int >> 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 -= 1; int previous = S[pos] - 'a' ; int current = c - 'a' ; S = S.Substring(0, pos) + c + S.Substring(pos + 1); hMap[previous].Remove(pos); if (!hMap.ContainsKey(current)) { hMap[current] = new List< int >(); } hMap[current].Add(pos); } // Utility function to determine number of different characters in given range. public static void Query2(Dictionary< int , List< int >> hMap, int L, int R) { // Iterate over all 26 alphabets // and check if it is in given range using floor() method. int count = 0; L -= 1; R -= 1; for ( int i = 0; i < 26; i++) { if (hMap.ContainsKey(i)) { var temp = hMap[i].Where(x => x <= R && x >= L).ToList(); if (temp.Count > 0) { count += 1; } } } Console.WriteLine(count); } } // This code is contributed by codebraxnzt |
Javascript
function main() { const S = 'abcdbbd' ; const N = S.length; const hMap = new Map(); // 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); } // Utility function to add the // position of all characters // of string into TreeSet function insert(hMap, S, N) { for (let i = 0; i < N; i++) { const c = S.charCodeAt(i) - 97; if (!hMap.has(c)) { hMap.set(c, new Set()); } hMap.get(c).add(i); } } // Utility function for update // the character at position P function query1(S, hMap, pos, c) { // We delete the position of the // previous character as new // character is to be replaced // at the same position. pos--; const previous = S.charCodeAt(pos) - 97; const current = c.charCodeAt(0) - 97; const chars = S.split( '' ); chars[pos] = c; S = chars.join( '' ); hMap.get(previous). delete (pos); if (!hMap.has(current)) { hMap.set(current, new Set()); } hMap.get(current).add(pos); } // Utility function to determine // number of different characters // in given range. function query2(hMap, L, R) { // Iterate over all 26 alphabets // and check if it is in given // range using floor() method. let count = 0; L--; R--; for (let i = 0; i < 26; i++) { if (hMap.has(i)) { const temp = Math.max(...Array.from(hMap.get(i)).filter(x => x <= R)); if (temp >= L) { count++; } } } console.log(count); } main(); |
3 1 5
Time complexity: O(Q * logN) where Q is number of queries and N is the size of the string.
Space complexity: O(NlogN), where N is the length of the string.