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 Xvoid Query1(string& S, int i, char X) { S[i - 1] = X; }// Driver codeint 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 Xdef Query1(S, i, X): S[i - 1] = X# Driver codeif __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) |
Output
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_setint 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 setvoid 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 Pvoid 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 codeint 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 codeimport collections# Insert all characters with its# occurrence in the hash mapdef 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 Pdef 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 approachusing 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 TreeSetfunction 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 Pfunction 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(); |
Output
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.
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!
