Dada una string S , la tarea es encontrar la string lexicográfica más grande con no más de K ocurrencias consecutivas de un elemento reorganizando o eliminando los elementos.
Ejemplos:
Entrada: S = “baccc”
K = 2
Salida: Resultado = “ccbca”
Explicación: Dado que K=2, se pueden colocar un máximo de 2 caracteres iguales consecutivamente.
No. de ‘c’ = 3.
No. de ‘b’ = 1.
No. de ‘a’ = 1.
Dado que se tiene que imprimir la string lexicográfica más grande, la respuesta es “ccbca”.Entrada: S = “xxxxzaz”
K = 3
Salida: resultado = “zzxxxax”
Acercarse:
- Forme una array de frecuencias de tamaño 26, donde el índice i se elige usando (un carácter en una string: ‘a’).
- Inicialice una string vacía para almacenar los cambios correspondientes.
- Para i=25 a 0, haz:
- Si la frecuencia en el índice i es mayor que k, agregue (i + ‘a’) K veces. Disminuya la frecuencia en K en el índice i. encuentre el siguiente elemento de mayor prioridad y agregue para responder y disminuya la frecuencia en el índice respectivo en 1.
- Si la frecuencia en el índice i es mayor que 0 pero menor que k, agregue (i + ‘a’) por su frecuencia.
- Si la frecuencia en el índice i es 0, entonces ese índice no se puede usar para formar un elemento y, por lo tanto, verificar el siguiente elemento de mayor prioridad posible.
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define ll long long int // Function to find the // largest lexicographical // string with given constraints. string getLargestString(string s, ll k) { // vector containing frequency // of each character. vector<int> frequency_array(26, 0); // assigning frequency to for (int i = 0; i < s.length(); i++) { frequency_array[s[i] - 'a']++; } // empty string of string class type string ans = ""; // loop to iterate over // maximum priority first. for (int i = 25; i >= 0;) { // if frequency is greater than // or equal to k. if (frequency_array[i] > k) { // temporary variable to operate // in-place of k. int temp = k; string st(1, i + 'a'); while (temp > 0) { // concatenating with the // resultant string ans. ans += st; temp--; } frequency_array[i] -= k; // handling k case by adjusting // with just smaller priority // element. int j = i - 1; while (frequency_array[j] <= 0 && j >= 0) { j--; } // condition to verify if index // j does have frequency // greater than 0; if (frequency_array[j] > 0 && j >= 0) { string str(1, j + 'a'); ans += str; frequency_array[j] -= 1; } else { // if no such element is found // than string can not be // processed further. break; } } // if frequency is greater than 0 // and less than k. else if (frequency_array[i] > 0) { // here we don't need to fix K // consecutive element criteria. int temp = frequency_array[i]; frequency_array[i] -= temp; string st(1, i + 'a'); while (temp > 0) { ans += st; temp--; } } // otherwise check for next // possible element. else { i--; } } return ans; } // Driver program int main() { string S = "xxxxzza"; int k = 3; cout << getLargestString(S, k) << endl; return 0; }
Java
// Java code for // the above approach import java.util.*; class GFG{ // Function to find the // largest lexicographical // String with given constraints. static String getLargestString(String s, int k) { // Vector containing frequency // of each character. int []frequency_array = new int[26]; // Assigning frequency for (int i = 0; i < s.length(); i++) { frequency_array[s.charAt(i) - 'a']++; } // Empty String of // String class type String ans = ""; // Loop to iterate over // maximum priority first. for (int i = 25; i >= 0😉 { // If frequency is greater than // or equal to k. if (frequency_array[i] > k) { // Temporary variable to // operate in-place of k. int temp = k; String st = String.valueOf((char)(i + 'a')); while (temp > 0) { // Concatenating with the // resultant String ans. ans += st; temp--; } frequency_array[i] -= k; // Handling k case by adjusting // with just smaller priority // element. int j = i - 1; while (frequency_array[j] <= 0 && j >= 0) { j--; } // Condition to verify if index // j does have frequency // greater than 0; if (frequency_array[j] > 0 && j >= 0) { String str = String.valueOf((char)(j + 'a')); ans += str; frequency_array[j] -= 1; } else { // If no such element is found // than String can not be // processed further. break; } } // If frequency is greater than 0 // and less than k. else if (frequency_array[i] > 0) { // Here we don't need to fix K // consecutive element criteria. int temp = frequency_array[i]; frequency_array[i] -= temp; String st = String.valueOf((char)(i + 'a')); while (temp > 0) { ans += st; temp--; } } // Otherwise check for next // possible element. else { i--; } } return ans; } // Driver code public static void main(String[] args) { String S = "xxxxzza"; int k = 3; System.out.print(getLargestString(S, k)); } } // This code is contributed by shikhasingrajput
Python3
# Python3 code for the above approach # Function to find the # largest lexicographical # string with given constraints. def getLargestString(s, k): # Vector containing frequency # of each character. frequency_array = [0] * 26 # Assigning frequency to for i in range(len(s)): frequency_array[ord(s[i]) - ord('a')] += 1 # Empty string of # string class type ans = "" # Loop to iterate over # maximum priority first. i = 25 while i >= 0: # If frequency is greater than # or equal to k. if (frequency_array[i] > k): # Temporary variable to # operate in-place of k. temp = k st = chr( i + ord('a')) while (temp > 0): # concatenating with the # resultant string ans. ans += st temp -= 1 frequency_array[i] -= k # Handling k case by adjusting # with just smaller priority # element. j = i - 1 while (frequency_array[j] <= 0 and j >= 0): j -= 1 # Condition to verify if index # j does have frequency # greater than 0; if (frequency_array[j] > 0 and j >= 0): str1 = chr(j + ord( 'a')) ans += str1 frequency_array[j] -= 1 else: # if no such element is found # than string can not be # processed further. break # If frequency is greater than 0 #and less than k. elif (frequency_array[i] > 0): # Here we don't need to fix K # consecutive element criteria. temp = frequency_array[i] frequency_array[i] -= temp st = chr(i + ord('a')) while (temp > 0): ans += st temp -= 1 # Otherwise check for next # possible element. else: i -= 1 return ans # Driver code if __name__ == "__main__": S = "xxxxzza" k = 3 print (getLargestString(S, k)) # This code is contributed by Chitranayal
C#
// C# code for // the above approach using System; class GFG{ // Function to find the // largest lexicographical // String with given constraints. static String getLargestString(String s, int k) { // List containing frequency // of each character. int []frequency_array = new int[26]; // Assigning frequency for (int i = 0; i < s.Length; i++) { frequency_array[s[i] - 'a']++; } // Empty String of // String class type String ans = ""; // Loop to iterate over // maximum priority first. for (int i = 25; i >= 0;) { // If frequency is greater than // or equal to k. if (frequency_array[i] > k) { // Temporary variable to // operate in-place of k. int temp = k; String st = String.Join("", (char)(i + 'a')); while (temp > 0) { // Concatenating with the // resultant String ans. ans += st; temp--; } frequency_array[i] -= k; // Handling k case by adjusting // with just smaller priority // element. int j = i - 1; while (frequency_array[j] <= 0 && j >= 0) { j--; } // Condition to verify if index // j does have frequency // greater than 0; if (frequency_array[j] > 0 && j >= 0) { String str = String.Join("", (char)(j + 'a')); ans += str; frequency_array[j] -= 1; } else { // If no such element is found // than String can not be // processed further. break; } } // If frequency is greater than 0 // and less than k. else if (frequency_array[i] > 0) { // Here we don't need to fix K // consecutive element criteria. int temp = frequency_array[i]; frequency_array[i] -= temp; String st = String.Join("", (char)(i + 'a')); while (temp > 0) { ans += st; temp--; } } // Otherwise check for next // possible element. else { i--; } } return ans; } // Driver code public static void Main(String[] args) { String S = "xxxxzza"; int k = 3; Console.Write(getLargestString(S, k)); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript code for // the above approach // Function to find the // largest lexicographical // String with given constraints. function getLargestString(s,k) { // Vector containing frequency // of each character. let frequency_array = new Array(26); for(let i=0;i<26;i++) { frequency_array[i]=0; } // Assigning frequency for (let i = 0; i < s.length; i++) { frequency_array[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } // Empty String of // String class type let ans = ""; // Loop to iterate over // maximum priority first. for (let i = 25; i >= 0;) { // If frequency is greater than // or equal to k. if (frequency_array[i] > k) { // Temporary variable to // operate in-place of k. let temp = k; let st = String.fromCharCode(i + 'a'.charCodeAt(0)); while (temp > 0) { // Concatenating with the // resultant String ans. ans += st; temp--; } frequency_array[i] -= k; // Handling k case by adjusting // with just smaller priority // element. let j = i - 1; while (frequency_array[j] <= 0 && j >= 0) { j--; } // Condition to verify if index // j does have frequency // greater than 0; if (frequency_array[j] > 0 && j >= 0) { let str = String.fromCharCode(j + 'a'.charCodeAt(0)); ans += str; frequency_array[j] -= 1; } else { // If no such element is found // than String can not be // processed further. break; } } // If frequency is greater than 0 // and less than k. else if (frequency_array[i] > 0) { // Here we don't need to fix K // consecutive element criteria. let temp = frequency_array[i]; frequency_array[i] -= temp; let st = String.fromCharCode(i + 'a'.charCodeAt(0)); while (temp > 0) { ans += st; temp--; } } // Otherwise check for next // possible element. else { i--; } } return ans; } // Driver code let S = "xxxxzza"; let k = 3; document.write(getLargestString(S, k)); // This code is contributed by avanitrachhadiya2155 </script>
Producción
zzxxxax
Complejidad de tiempo: O(N)