Given a string str of length N, and Q queries of the following two types:
- (1 L R K): Find the Kth greatest character (non-distinct) from the range of indices [L, R] (1-based indexing)
- (2 J C): Replace the Jth character from the string by character C.
Examples:
Input: str = “abcddef”, Q = 3, queries[][] = {{1, 2, 5, 3}, {2, 4, g}, {1, 1, 4, 3}}
Output:
c
b
Explanation :
Query 1: String between indices (2, 5) is “bcdd”. The third largest character is ‘c’. Therefore, c is the required output.
Query 2: Replace S[4] by ‘g’. Therefore, S modifies to “abcgdef”.
Query 3: String between indices (1, 4) is “abcg”. The third largest character is ‘b’. Therefore, b is the required output.Input: str=” afcdehgk”, Q = 4, queries[][] = {{1, 2, 5, 4}, {2, 5, m}, {1, 3, 7, 2}, {1, 1, 6, 4}}
Output:
c
h
d
Naive Approach: The simplest approach to solve the problem is as follows:
- For each query of type ( 1 L R K ), find the substring of S from the range of indices [L, R], and sort this substring in non-increasing order. Print the character at the Kth index in the substring.
- For each query of type ( 2 J C ), replace the Jth character in S by C.
C++
// C++ code for the approach#include <bits/stdc++.h>#include <algorithm>#include <string>using namespace std;// Function to print the Kth greatest characterchar printCharacter(string &str, int L, int R, int K) { // Extract the substring from [L, R] string substr = str.substr(L - 1, R - L + 1); // Sort the substring in non-increasing order sort(substr.begin(), substr.end(), greater<char>()); // return the Kth character return substr[K - 1];}// Function to update the Jth character of the stringvoid updateString(string &str, int J, char C) { // Update the Jth character str[J - 1] = C;}// Driver Codeint main() { // Given string string str = "abcddef"; // Count of queries int Q = 3; // Queries cout << printCharacter(str, 1, 2, 2) << endl; updateString(str, 4, 'g'); cout << printCharacter(str, 1, 5, 4) << endl; return 0;} |
Java
// Java code for the approachimport java.util.*;public class GFG { // Function to print the Kth greatest character public static char printCharacter(String str, int L, int R, int K) { // Extract the substring from [L, R] String substr = str.substring(L - 1, R); // Sort the substring in non-increasing order char[] charArr = substr.toCharArray(); Arrays.sort(charArr); String sortedStr = new String(charArr); String revStr = new StringBuilder(sortedStr) .reverse() .toString(); // return the Kth character return revStr.charAt(K - 1); } // Function to update the Jth character of the string public static void updateString(StringBuilder str, int J, char C) { // Update the Jth character str.setCharAt(J - 1, C); } // Driver Code public static void main(String[] args) { // Given string String str = "abcddef"; // Count of queries int Q = 3; // Queries System.out.println(printCharacter(str, 1, 2, 2)); StringBuilder sb = new StringBuilder(str); updateString(sb, 4, 'g'); str = sb.toString(); System.out.println(printCharacter(str, 1, 5, 4)); }} |
Python3
# Python3 code for the approach# Function to print the Kth greatest characterdef printCharacter(string, L, R, K): # Extract the substring from [L, R] substr = string[L-1:R] # Sort the substring in non-increasing order substr = sorted(substr, reverse=True) # Return the Kth character return substr[K-1]# Function to update the Jth character of the stringdef updateString(string, J, C): # Update the Jth character string = string[:J-1] + C + string[J:] # Driver Codeif __name__ == '__main__': # Given string string = "abcddef" # Count of queries Q = 3 # Queries print(printCharacter(string, 1, 2, 2)) updateString(string, 4, 'g') print(printCharacter(string, 1, 5, 4)) |
C#
// C# code for the approachusing System;class Program { // Function to print the Kth greatest character static char PrintCharacter(string str, int L, int R, int K) { // Extract the substring from [L, R] string substr = str.Substring(L - 1, R - L + 1); // Convert the substring to a character array char[] chars = substr.ToCharArray(); // Sort the character array in non-increasing order Array.Sort(chars); Array.Reverse(chars); // Return the Kth character return chars[K - 1]; } // Function to update the Jth character of the string static string UpdateString(string str, int J, char C) { // Update the Jth character char[] chars = str.ToCharArray(); chars[J - 1] = C; // Convert the character array back to a string and // return it return new string(chars); } static void Main(string[] args) { // Given string string str = "abcddef"; // Count of queries int Q = 3; // Queries Console.WriteLine(PrintCharacter(str, 1, 2, 2)); str = UpdateString(str, 4, 'g'); Console.WriteLine(PrintCharacter(str, 1, 5, 4)); }} |
Javascript
// JavaScript code for the approach// Function to print the Kth greatest characterfunction printCharacter(str, L, R, K) { // Extract the substring from [L, R] let substr = str.substring(L - 1, R); // Sort the substring in non-increasing order substr = substr.split('').sort(function(a, b) { return b.localeCompare(a); }).join(''); // return the Kth character return substr.charAt(K - 1);}// Function to update the Jth character of the stringfunction updateString(str, J, C) { // Update the Jth character str = str.substring(0, J - 1) + C + str.substring(J); return str;}// Driver Codelet str = "abcddef";// Count of querieslet Q = 3;// Queriesconsole.log(printCharacter(str, 1, 2, 2));str = updateString(str, 4, 'g');console.log(printCharacter(str, 1, 5, 4));// This code is contributed by user_dtewbxkn77n |
Output
a b
Time Complexity: O ( Q * ( N log(N) ) ), where N logN is the computational complexity of sorting each substring.
Auxiliary Space: O(N)
The below code is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include "bits/stdc++.h"using namespace std;// Function to find the kth greatest// character from the strijngchar find_kth_largest(string str, int k){ // Sorting the string in // non-increasing Order sort(str.begin(), str.end(), greater<char>()); return str[k - 1];}// Function to print the K-th character// from the substring S[l] .. S[r]char printCharacter(string str, int l, int r, int k){ // 0-based indexing l = l - 1; r = r - 1; // Substring of str from the // indices l to r. string temp = str.substr(l, r - l + 1); // Extract kth Largest character char ans = find_kth_largest(temp, k); return ans;}// Function to replace character at// pos of str by the character svoid updateString(string str, int pos, char s){ // Index of S to be updated. int index = pos - 1; char c = s; // Character to be replaced // at index in S str[index] = c;}// Driver Codeint main(){ // Given string string str = "abcddef"; // Count of queries int Q = 3; // Queries cout << printCharacter(str, 1, 2, 2) << endl; updateString(str, 4, 'g'); cout << printCharacter(str, 1, 5, 4) << endl; return 0;} |
Java
// Java Program to implement// the above approach//include "bits/stdJava.h"import java.util.*;class GFG{// Function to find the kth greatest// character from the strijngstatic char find_kth_largest(char []str, int k){ // Sorting the String in // non-increasing Order Arrays.sort(str); reverse(str); return str[k - 1];} static char[] reverse(char a[]) { int i, n = a.length; char t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;} // Function to print the K-th character// from the subString S[l] .. S[r]static char printCharacter(String str, int l, int r, int k){ // 0-based indexing l = l - 1; r = r - 1; // SubString of str from the // indices l to r. String temp = str.substring(l, r - l + 1); // Extract kth Largest character char ans = find_kth_largest(temp.toCharArray(), k); return ans;}// Function to replace character at// pos of str by the character sstatic void updateString(char []str, int pos, char s){ // Index of S to be updated. int index = pos - 1; char c = s; // Character to be replaced // at index in S str[index] = c;}// Driver Codepublic static void main(String[] args){ // Given String String str = "abcddef"; // Count of queries int Q = 3; // Queries System.out.print(printCharacter(str, 1, 2, 2) + "\n"); updateString(str.toCharArray(), 4, 'g'); System.out.print(printCharacter(str, 1, 5, 4) + "\n");}}// This code is contributed by shikhasingrajput |
Python3
# Python3 Program to implement# the above approach# Function to find the kth greatest# character from the stringdef find_kth_largest(strr, k): # Sorting the in # non-increasing Order strr = sorted(strr) strr = strr[:: -1] return strr[k - 1]# Function to print the K-th character# from the subS[l] .. S[r]def printCharacter(strr, l, r, k): #0-based indexing l = l - 1 r = r - 1 # Subof strr from the # indices l to r. temp= strr[l: r - l + 1] #Extract kth Largest character ans = find_kth_largest(temp, k) return ans# Function to replace character at# pos of strr by the character sdef updateString(strr, pos, s): # Index of S to be updated. index = pos - 1 c = s # Character to be replaced # at index in S strr[index] = c# Driver Codeif __name__ == '__main__': # Given string strr = "abcddef" strr=[i for i in strr] # Count of queries Q = 3 # Queries print(printCharacter(strr, 1, 2, 2)) updateString(strr, 4, 'g') print(printCharacter(strr, 1, 5, 4))# This code is contributed by Mohit Kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the kth greatest// character from the stringstatic char find_kth_largest(char []str, int k){ // Sorting the String in // non-increasing Order Array.Sort(str); reverse(str); return str[k - 1];}static char[] reverse(char []a) { int i, n = a.Length; char t; for(i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Function to print the K-th character// from the subString S[l] .. S[r]static char printchar(String str, int l, int r, int k){ // 0-based indexing l = l - 1; r = r - 1; // SubString of str from the // indices l to r. String temp = str.Substring(l, r - l + 1); // Extract kth Largest character char ans = find_kth_largest( temp.ToCharArray(), k); return ans;}// Function to replace character at// pos of str by the character sstatic void updateString(char []str, int pos, char s){ // Index of S to be updated. int index = pos - 1; char c = s; // char to be replaced // at index in S str[index] = c;}// Driver Codepublic static void Main(String[] args){ // Given String String str = "abcddef"; // Count of queries //int Q = 3; // Queries Console.Write(printchar(str, 1, 2, 2) + "\n"); updateString(str.ToCharArray(), 4, 'g'); Console.Write(printchar(str, 1, 5, 4) + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript Program to implement// the above approach//include "bits/stdJava.h"// Function to find the kth greatest// character from the strijngfunction find_kth_largest(str,k){ // Sorting the String in // non-increasing Order str.sort(); reverse(str); return str[k - 1];}function reverse(a){ let i, n = a.length; let t; for (i = 0; i < Math.floor(n / 2); i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a;}// Function to print the K-th character// from the subString S[l] .. S[r]function printCharacter(str,l,r,k){ // 0-based indexing l = l - 1; r = r - 1; // SubString of str from the // indices l to r. let temp = str.substring(l, r - l + 1); // Extract kth Largest character let ans = find_kth_largest(temp.split(""), k); return ans;}// Function to replace character at// pos of str by the character sfunction updateString(str,pos,s){ // Index of S to be updated. let index = pos - 1; let c = s; // Character to be replaced // at index in S str[index] = c;}// Driver Code// Given Stringlet str = "abcddef";// Count of querieslet Q = 3;// Queriesdocument.write(printCharacter(str, 1, 2, 2) + "<br>");updateString(str.split(""), 4, 'g');document.write(printCharacter(str, 1, 5, 4) + "<br>");// This code is contributed by avanitrachhadiya2155</script> |
Output:
a b
Time Complexity: O(Q(r – l + 1) log (r – l + 1)) + O(Q), where Q is the number of queries, and r and l are the endpoints of the substring in each query.
Space Complexity: O(1)
Efficient Approach: The above approach can be optimized by precomputing the count of all the characters which are greater than or equal to character C ( ‘a’ ? C ? ‘z’ ) efficiently using a Fenwick Tree.
Follow the steps below to solve the problem:
- Create a Fenwick Tree to store the frequencies of all characters from ‘a’ to ‘z‘
- For every query of type 1, check for each character from ‘z’ to ‘a’, whether it is the Kth the greatest character.
- In order to perform this, traverse from ‘z’ to ‘a’ and for each character, check if the count of all the characters traversed becomes ? K or not. Print the character for which the count becomes ? K.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include "bits/stdc++.h"using namespace std;// Maximum Size of a Stringconst int maxn = 100005;// Fenwick Tree to store the// frequencies of 26 alphabetsint BITree[26][maxn];// Size of the String.int N;// Function to update Fenwick Tree for// Character c at index valvoid update_BITree(int index, char C, int val){ while (index <= N) { // Add val to current node // Fenwick Tree BITree[C - 'a'][index] += val; // Move index to parent node // in update View index += (index & -index); }}// Function to get sum of frequencies// of character c till indexint sum_BITree(int index, char C){ // Stores the sum int s = 0; while (index) { // Add current element of // Fenwick tree to sum s += BITree[C - 'a'][index]; // Move index to parent node // in getSum View index -= (index & -index); } return s;}// Function to create the Fenwick treevoid buildTree(string str){ for (int i = 1; i <= N; i++) { update_BITree(i, str[i], 1); } cout << endl;}// Function to print the kth largest// character in the range of l to rchar printCharacter(string str, int l, int r, int k){ // Stores the count of // characters int count = 0; // Stores the required // character char ans; for (char C = 'z'; C >= 'a'; C--) { // Calculate frequency of // C in the given range int times = sum_BITree(r, C) - sum_BITree(l - 1, C); // Increase count count += times; // If count exceeds K if (count >= k) { // Required character // found ans = C; break; } } return ans;}// Function to update character// at pos by character svoid updateTree(string str, int pos, char s){ // 0 based index system int index = pos; update_BITree(index, str[index], -1); str[index] = s; update_BITree(index, s, 1);}// Driver Codeint main(){ string str = "abcddef"; N = str.size(); // Makes the string 1-based indexed str = '#' + str; // Number of queries int Q = 3; // Construct the Fenwick Tree buildTree(str); cout << printCharacter(str, 1, 2, 2) << endl; updateTree(str, 4, 'g'); cout << printCharacter(str, 1, 5, 4) << endl; return 0;} |
Java
// Java Program to implement// the above approach//include "bits/stdJava.h"import java.util.*;class GFG{// Maximum Size of a Stringstatic int maxn = 100005;// Fenwick Tree to store the// frequencies of 26 alphabetsstatic int [][]BITree = new int[26][maxn];// Size of the String.static int N;// Function to update Fenwick Tree for// Character c at index valstatic void update_BITree(int index, char C, int val){ while (index <= N) { // Add val to current node // Fenwick Tree BITree[C - 'a'][index] += val; // Move index to parent node // in update View index += (index & -index); }}// Function to get sum of frequencies// of character c till indexstatic int sum_BITree(int index, char C){ // Stores the sum int s = 0; while (index > 0) { // Add current element of // Fenwick tree to sum s += BITree[C - 'a'][index]; // Move index to parent node // in getSum View index -= (index & -index); } return s;}// Function to create the Fenwick treestatic void buildTree(String str){ for (int i = 1; i <= N; i++) { update_BITree(i, str.charAt(i), 1); } System.out.println();}// Function to print the kth largest// character in the range of l to rstatic char printCharacter(String str, int l, int r, int k){ // Stores the count of // characters int count = 0; // Stores the required // character char ans = 0; for (char C = 'z'; C >= 'a'; C--) { // Calculate frequency of // C in the given range int times = sum_BITree(r, C) - sum_BITree(l - 1, C); // Increase count count += times; // If count exceeds K if (count >= k) { // Required character // found ans = C; break; } } return ans;}// Function to update character// at pos by character sstatic void updateTree(String str, int pos, char s){ // 0 based index system int index = pos; update_BITree(index, str.charAt(index), -1); str = str.substring(0, index) + s + str.substring(index + 1); update_BITree(index, s, 1);}// Driver Codepublic static void main(String[] args){ String str = "abcddef"; N = str.length(); // Makes the String 1-based indexed str = '/' + str; // Number of queries int Q = 3; // Construct the Fenwick Tree buildTree(str); System.out.print(printCharacter(str, 1, 2, 2) + "\n"); updateTree(str, 4, 'g'); System.out.print(printCharacter(str, 1, 5, 4) + "\n");}}// This code is contributed by shikhasingrajput |
Python3
# Python3 Program to implement# the above approach# Maximum Size of a Stringmaxn = 100005# Fenwick Tree to store the# frequencies of 26 alphabetsBITree = [[0 for x in range(maxn)] for y in range(26)]# Size of the String.N = 0# Function to update Fenwick Tree for# Character c at index valdef update_BITree(index, C, val): while (index <= N): # Add val to current node # Fenwick Tree BITree[ord(C) - ord('a')][index]+= val # Move index to parent node # in update View index += (index & -index)# Function to get sum of # frequencies of character # c till indexdef sum_BITree(index, C): # Stores the sum s = 0 while (index): # Add current element of # Fenwick tree to sum s += BITree[ord(C) - ord('a')][index] # Move index to parent node # in getSum View index -= (index & -index) return s# Function to create # the Fenwick treedef buildTree(st): for i in range(1, N + 1): update_BITree(i, st[i], 1) print()# Function to print the # kth largest character # in the range of l to rdef printCharacter(st, l, r, k): # Stores the count of # characters count = 0 for C in range(ord('z'), ord('a') - 1, -1): # Calculate frequency of # C in the given range times = (sum_BITree(r, chr(C)) - sum_BITree(l - 1, chr(C))) # Increase count count += times # If count exceeds K if (count >= k): # Required character # found ans = chr( C) break return ans# Function to update character# at pos by character sdef updateTree(st, pos, s): # 0 based index system index = pos; update_BITree(index, st[index], -1) st.replace(st[index], s, 1) update_BITree(index, s, 1)# Driver Codeif __name__ == "__main__": st = "abcddef" N = len(st) # Makes the string # 1-based indexed st = '#' + st # Number of queries Q = 3 # Construct the Fenwick Tree buildTree(st) print (printCharacter(st, 1, 2, 2)) updateTree(st, 4, 'g') print (printCharacter(st, 1, 5, 4))# This code is contributed by Chitranayal |
C#
// C# Program to implement// the above approachusing System;class GFG{// Maximum Size of a Stringstatic int maxn = 100005;// Fenwick Tree to store the// frequencies of 26 alphabetsstatic int [,]BITree = new int[26, maxn];// Size of the String.static int N;// Function to update Fenwick Tree for// char c at index valstatic void update_BITree(int index, char C, int val){ while (index <= N) { // Add val to current node // Fenwick Tree BITree[C - 'a', index] += val; // Move index to parent node // in update View index += (index & -index); }}// Function to get sum of frequencies// of character c till indexstatic int sum_BITree(int index, char C){ // Stores the sum int s = 0; while (index > 0) { // Add current element of // Fenwick tree to sum s += BITree[C - 'a', index]; // Move index to parent node // in getSum View index -= (index & -index); } return s;}// Function to create the Fenwick treestatic void buildTree(String str){ for (int i = 1; i <= N; i++) { update_BITree(i, str[i], 1); } Console.WriteLine();}// Function to print the kth largest// character in the range of l to rstatic char printchar(String str, int l, int r, int k){ // Stores the count of // characters int count = 0; // Stores the required // character char ans = (char)0; for (char C = 'z'; C >= 'a'; C--) { // Calculate frequency of // C in the given range int times = sum_BITree(r, C) - sum_BITree(l - 1, C); // Increase count count += times; // If count exceeds K if (count >= k) { // Required character // found ans = C; break; } } return ans;}// Function to update character// at pos by character sstatic void updateTree(String str, int pos, char s){ // 0 based index system int index = pos; update_BITree(index, str[index], -1); str = str.Substring(0, index) + s + str.Substring(index + 1); update_BITree(index, s, 1);}// Driver Codepublic static void Main(String[] args){ String str = "abcddef"; N = str.Length; // Makes the String 1-based indexed str = '/' + str; // Number of queries int Q = 3; // Construct the Fenwick Tree buildTree(str); Console.Write(printchar(str, 1, 2, 2) + "\n"); updateTree(str, 4, 'g'); Console.Write(printchar(str, 1, 5, 4) + "\n");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript Program to implement// the above approach // Maximum Size of a Stringlet maxn = 100005;// Fenwick Tree to store the// frequencies of 26 alphabetslet BITree = new Array(26);for(let i=0;i<26;i++){ BITree[i]=new Array(maxn); for(let j=0;j<maxn;j++) { BITree[i][j]=0; } }// Size of the String.let N;// Function to update Fenwick Tree for// Character c at index valfunction update_BITree(index,C,val){ while (index <= N) { // Add val to current node // Fenwick Tree BITree[C.charCodeAt(0) - 'a'.charCodeAt(0)][index] += val; // Move index to parent node // in update View index += (index & -index); }}// Function to get sum of frequencies// of character c till indexfunction sum_BITree(index,C){ // Stores the sum let s = 0; while (index > 0) { // Add current element of // Fenwick tree to sum s += BITree[C.charCodeAt(0) - 'a'.charCodeAt(0)][index]; // Move index to parent node // in getSum View index -= (index & -index); } return s;}// Function to create the Fenwick treefunction buildTree(str){ for (let i = 1; i <= N; i++) { update_BITree(i, str[i], 1); } document.write("<br>");}// Function to print the kth largest// character in the range of l to rfunction printCharacter(str,l,r,k){ // Stores the count of // characters let count = 0; // Stores the required // character let ans = 0; for (let C = 'z'.charCodeAt(0); C >= 'a'.charCodeAt(0); C--) { // Calculate frequency of // C in the given range let times = sum_BITree(r, String.fromCharCode(C)) - sum_BITree(l - 1, String.fromCharCode(C)); // Increase count count += times; // If count exceeds K if (count >= k) { // Required character // found ans = String.fromCharCode(C); break; } } return ans;}// Function to update character// at pos by character sfunction updateTree(str,pos,s){ // 0 based index system let index = pos; update_BITree(index, str[index], -1); str = str.substring(0, index) + s + str.substring(index + 1); update_BITree(index, s, 1);}// Driver Codelet str = "abcddef";N = str.length;// Makes the String 1-based indexedstr = '/' + str;// Number of querieslet Q = 3;// Construct the Fenwick TreebuildTree(str);document.write(printCharacter(str, 1, 2, 2) + "<br>");updateTree(str, 4, 'g');document.write(printCharacter(str, 1, 5, 4) + "<br>");// This code is contributed by rag2127</script> |
Output:
a b
Time Complexity: O( QlogN + NlogN )
Auxiliary Space: O(26 * maxn), where maxn denotes the maximum possible 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!
