Frequency of lexicographically Kth smallest character in the a string
Given a string S of length N and an integer K, the task is to find the frequency of the lexicographically Kth smallest character present in the given string.
Examples:
Input: S = “w3wiki”, K = 3
Output: 4
Explanation: The lexicographically 3rd smallest character in S is ‘e’. Frequency of ‘e’ in S = 4.Input: S = “abcdabcd”, K = 4
Output: 2
Explanation: The lexicographically 4th smallest lexicographical character in S is ‘b’. Frequency of ‘b’ in S = 2.
Approach: The idea is to sort the string in ascending order of their ASCII values. Now, find the (K – 1)th character in the sorted string and find its frequency. Follow the steps below to solve the problem:
- Sort the given string S in ascending order.
- Store the (K – 1)th character in a variable ch, i.e. S[K – 1].
- Find the frequency of the character ch in S and print that value.
Below is the implementation of the approach:
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 = "w3wiki" ; 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 = "w3wiki" ; 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 = "w3wiki" ; 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 = "w3wiki" ; 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 = "w3wiki" ; var N = S.length; var K = 3; KthCharacter(S, N, K); // This code is contributed by famously </script> |
Output:
4
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Contact Us