Dada una string S de longitud N y un entero K , la tarea es encontrar la frecuencia del K -ésimo carácter lexicográficamente más pequeño presente en la string dada.
Ejemplos:
Entrada: S = “geeksforgeeks”, K = 3
Salida: 4
Explicación: Lexicográficamente , el tercer carácter más pequeño de S es ‘e’. Frecuencia de ‘e’ en S = 4.Entrada: S = “abcdabcd”, K = 4
Salida: 2
Explicación: El 4º carácter lexicográfico más pequeño lexicográficamente en S es ‘b’. Frecuencia de ‘b’ en S = 2.
Enfoque: La idea es ordenar la string en orden ascendente de sus valores ASCII . Ahora, busque el carácter (K – 1) enésima en la string ordenada y encuentre su frecuencia. Siga los pasos a continuación para resolver el problema:
- Ordene la string dada S en orden ascendente.
- Almacene el carácter (K – 1) en una variable ch , es decir, S [K – 1] .
- Encuentre la frecuencia del carácter ch en S e imprima ese valor.
A continuación se muestra la implementación del enfoque:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the frequency of // the lexicographically Kth smallest // character void KthCharacter( string S, int N, int K) { // Convert the string to // array of characters char strarray[N + 1]; strcpy(strarray, S.c_str()); // Sort the array in ascending order sort(strarray, strarray + N); // Store the Kth character char ch = strarray[K - 1]; // Store the frequency of // the K-th character int count = 0; // Count the frequency of // the K-th character for (auto c : strarray) { if (c == ch) count++; } // Print the count cout << count; } // Driver Code int main() { string S = "geeksforgeeks"; int N = S.length(); int K = 3; KthCharacter(S, N, K); return 0; } // This code is contributed by sanjoy_62.
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to find the frequency of // the lexicographically Kth smallest // character public static void KthCharacter( String S, int N, int K) { // Convert the string to // array of characters char strarray[] = S.toCharArray(); // Sort the array in ascending order Arrays.sort(strarray); // Store the Kth character char ch = strarray[K - 1]; // Store the frequency of // the K-th character int count = 0; // Count the frequency of // the K-th character for (char c : strarray) { if (c == ch) count++; } // Print the count System.out.println(count); } // Driver Code public static void main(String[] args) { String S = "geeksforgeeks"; int N = S.length(); int K = 3; KthCharacter(S, N, K); } }
Python3
# Python program for the above approach # Function to find the frequency of # the lexicographically Kth smallest # character def KthCharacter(S, N, K): # Convert the string to # array of characters strarray = [char for char in S]; # Sort the array in ascending order strarray.sort(); # Store the Kth character ch = strarray[K - 1]; # Store the frequency of # the K-th character count = 0; # Count the frequency of # the K-th character for c in strarray: if (c == ch): count += 1; # Print the count print(count); # Driver Code if __name__ == '__main__': S = "geeksforgeeks"; N = len(S); K = 3; KthCharacter(S, N, K); # This code is contributed by 29AjayKumar
C#
// C# program to implement // the above approach using System; class GFG { // Function to find the frequency of // the lexicographically Kth smallest // character public static void KthCharacter( string S, int N, int K) { // Convert the string to // array of characters char[] strarray = S.ToCharArray(); // Sort the array in ascending order Array.Sort(strarray); // Store the Kth character char ch = strarray[K - 1]; // Store the frequency of // the K-th character int count = 0; // Count the frequency of // the K-th character foreach (char c in strarray) { if (c == ch) count++; } // Print the count Console.Write(count); } // Driver Code public static void Main() { string S = "geeksforgeeks"; int N = S.Length; int K = 3; KthCharacter(S, N, K); } } // This code is contributed by splevel62.
Javascript
<script> // Javascript program for the above approach // Function to find the frequency of // the lexicographically Kth smallest // character function KthCharacter(S, N, K) { // Convert the string to // array of characters var strarray = S.split(''); strarray.sort(); // Store the Kth character var ch = strarray[K - 1]; // Store the frequency of // the K-th character var count = 0; // Count the frequency of // the K-th character strarray.forEach(c => { if (c == ch) count++; }); // Print the count document.write(count); } // Driver Code var S = "geeksforgeeks"; var N = S.length; var K = 3; KthCharacter(S, N, K); // This code is contributed by famously </script>
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA