Dada una string S y un rango L y R, la tarea es imprimir la string lexicográficamente más grande que se puede formar a partir de los caracteres en el rango L y R.
Ejemplos :
Input: str = "thgyfh", L = 2, R = 6 Output: yhhgf Input: str = "striver", L = 3, R = 5 Output: vri
Enfoque :
- Iterar de min(L, R) a max(L, R) y aumentar las frecuencias de los caracteres en una array freq[].
- Iterar de 25 a 0 e imprimir el número de veces que aparece cada carácter para obtener la string lexicográficamente más grande.
El punto común de error que todos cometen es que iteran de L a R en lugar de min(L, R) a max(L, R) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the // lexicographically largest string that // can be formed from the characters // in range L and R #include <bits/stdc++.h> using namespace std; // Function to return the lexicographically largest string string printLargestString(string s, int l, int r) { // hash array int freq[26] = { 0 }; // make 0-based indexing l--; r--; // iterate and count frequencies of character for (int i = min(l, r); i <= max(l, r); i++) { freq[s[i] - 'a']++; } // ans string string ans = ""; // iterate in frequency array for (int i = 25; i >= 0; i--) { // add till all characters // are added while (freq[i]) { ans += char('a' + i); freq[i]--; } } return ans; } // Driver Code int main() { string s = "striver"; int l = 3, r = 5; cout << printLargestString(s, l, r); return 0; }
Java
// Java program to print the // lexicographically largest String that // can be formed from the characters // in range L and R class GFG { // Function to return the lexicographically largest String static String printLargestString(String s, int l, int r) { // hash array int freq[] = new int[26]; // make 0-based indexing l--; r--; // iterate and count frequencies of character for (int i = Math.min(l, r); i <= Math.max(l, r); i++) { freq[s.charAt(i) - 'a']++; } // ans String String ans = ""; // iterate in frequency array for (int i = 25; i >= 0; i--) { // add till all characters // are added while (freq[i] > 0) { ans += (char) ('a' + i); freq[i]--; } } return ans; } // Driver Code public static void main(String[] args) { String s = "striver"; int l = 3, r = 5; System.out.println(printLargestString(s, l, r)); } } /* This JAVA code is contributed by 29AjayKumar*/
Python 3
# Python 3 program to print the # lexicographically largest string that # can be formed from the characters # in range L and R # Function to return the lexicographically # largest string def printLargestString(s, l, r): # hash array freq = [0] * 26 # make 0-based indexing l -= 1 r -= 1 # iterate and count frequencies of character for i in range(min(l, r), max(l, r) + 1) : freq[ord(s[i]) - ord('a')] += 1 # ans string ans = "" # iterate in frequency array for i in range(25, -1, -1): # add till all characters are added while (freq[i]): ans += chr(ord('a') + i) freq[i] -= 1 return ans # Driver Code if __name__ == "__main__": s = "striver" l = 3 r = 5 print(printLargestString(s, l, r)) # This code is contributed by ita_c
C#
// C# program to print the lexicographically // largest String that can be formed from the // characters in range L and R using System; class GFG { // Function to return the lexicographically // largest String static String printLargestString(String s, int l, int r) { // hash array int []freq = new int[26]; // make 0-based indexing l--; r--; // iterate and count frequencies // of character for (int i = Math.Min(l, r); i <= Math.Max(l, r); i++) { freq[s[i] - 'a']++; } // ans String String ans = ""; // iterate in frequency array for (int i = 25; i >= 0; i--) { // add till all characters // are added while (freq[i] > 0) { ans += (char) ('a' + i); freq[i]--; } } return ans; } // Driver Code public static void Main() { String s = "striver"; int l = 3, r = 5; Console.Write(printLargestString(s, l, r)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // javascript program to print the // lexicographically largest String that // can be formed from the characters // in range L and R // Function to return the lexicographically largest String function printLargestString( s , l , r) { // hash array var freq = Array(26).fill(0); // make 0-based indexing l--; r--; // iterate and count frequencies of character for (i = Math.min(l, r); i <= Math.max(l, r); i++) { freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // ans String var ans = ""; // iterate in frequency array for (var i = 25; i >= 0; i--) { // add till all characters // are added while (freq[i] > 0) { ans += String.fromCharCode('a'.charCodeAt(0) + i); freq[i]--; } } return ans; } // Driver Code var s = "striver"; var l = 3, r = 5; document.write(printLargestString(s, l, r)); // This code is contributed by todaysgaurav </script>
Producción:
vri
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces para contar las frecuencias.
Cada elemento se agrega a la tabla de frecuencia solo una vez, lo que toma O (1) y se agrega a la string que también toma O (1).
Espacio auxiliar: O (N), ya que estamos usando espacio adicional para almacenar la string resultante.