Dada una string str de longitud N, y Q consultas de los siguientes dos tipos:
- (1 LRK): Encuentre el K -ésimo carácter más grande ( no distinto ) del rango de índices [L, R] (indexación basada en 1)
- (2 JC): Reemplace el carácter J de la string por el carácter C.
Ejemplos:
Entrada: str = “abcddef”, Q = 3, consultas[][] = {{1, 2, 5, 3}, {2, 4, g}, {1, 1, 4, 3}}
Salida:
c
b
Explicación:
consulta 1: la string entre los índices (2, 5) es «bcdd». El tercer carácter más grande es ‘c’. Por lo tanto, c es la salida requerida.
Consulta 2: Reemplace S[4] por ‘g’. Por lo tanto, S se modifica a “abcgdef”.
Consulta 3: la string entre los índices (1, 4) es «abcg». El tercer carácter más grande es ‘b’. Por lo tanto, b es la salida requerida.Entrada: str=” afcdehgk”, Q = 4, consultas[][] = {{1, 2, 5, 4}, {2, 5, m}, {1, 3, 7, 2}, {1, 1, 6, 4}}
Salida:
c
h
d
Enfoque ingenuo: el enfoque más simple para resolver el problema es el siguiente:
- Para cada consulta de tipo ( 1 LRK ), busque la substring de S del rango de índices [L, R] y ordene esta substring en orden no creciente . Imprime el carácter en el índice K de la substring .
- Para cada consulta de tipo (2 JC) , reemplace el J -ésimo carácter en S por C.
Complejidad de tiempo: O ( Q * ( N log(N) ) ), donde N logN es la complejidad computacional de ordenar cada substring .
Espacio Auxiliar: O(N)
El siguiente código es la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include "bits/stdc++.h" using namespace std; // Function to find the kth greatest // character from the strijng char 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 s void 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 Code int 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 strijng static 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 s static 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 Code public 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 string def 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 s def 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 Code if __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 approach using System; class GFG{ // Function to find the kth greatest // character from the string static 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 s static 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 Code public 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 strijng function 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 s function 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 String let str = "abcddef"; // Count of queries let Q = 3; // Queries document.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>
a b
Enfoque eficiente: el enfoque anterior se puede optimizar calculando previamente el recuento de todos los caracteres que son mayores o iguales que el carácter C (‘a’ ≤ C ≤ ‘z’) de manera eficiente mediante un árbol Fenwick .
Siga los pasos a continuación para resolver el problema:
- Cree un árbol de Fenwick para almacenar las frecuencias de todos los caracteres de ‘ a’ a ‘z ‘
- Para cada consulta de tipo 1 , verifique para cada carácter de ‘z’ a ‘a’, si es el K -ésimo el carácter más grande.
- Para realizar esto, recorra de ‘z’ a ‘a’ y para cada carácter, verifique si el conteo de todos los caracteres recorridos es ≥ K o no. Imprime el carácter para el cual el conteo se convierte en ≥ K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include "bits/stdc++.h" using namespace std; // Maximum Size of a String const int maxn = 100005; // Fenwick Tree to store the // frequencies of 26 alphabets int BITree[26][maxn]; // Size of the String. int N; // Function to update Fenwick Tree for // Character c at index val 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 index int 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 tree void 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 r char 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 s void 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 Code int 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 String static int maxn = 100005; // Fenwick Tree to store the // frequencies of 26 alphabets static int [][]BITree = new int[26][maxn]; // Size of the String. static int N; // Function to update Fenwick Tree for // Character c at index val static 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 index static 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 tree static 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 r static 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 s static 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 Code public 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 String maxn = 100005 # Fenwick Tree to store the # frequencies of 26 alphabets BITree = [[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 val def 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 index def 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 tree def 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 r def 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 s def 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 Code if __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 approach using System; class GFG{ // Maximum Size of a String static int maxn = 100005; // Fenwick Tree to store the // frequencies of 26 alphabets static int [,]BITree = new int[26, maxn]; // Size of the String. static int N; // Function to update Fenwick Tree for // char c at index val static 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 index static 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 tree static 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 r static 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 s static 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 Code public 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 String let maxn = 100005; // Fenwick Tree to store the // frequencies of 26 alphabets let 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 val function 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 index function 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 tree function 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 r function 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 s function 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 Code let str = "abcddef"; N = str.length; // Makes the String 1-based indexed str = '/' + str; // Number of queries let Q = 3; // Construct the Fenwick Tree buildTree(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>
a b
Complejidad de tiempo: O( QlogN + NlogN )
Espacio auxiliar: O(26 * maxn), donde maxn denota la longitud máxima posible de la string.
Publicación traducida automáticamente
Artículo escrito por dbarnwal888 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA