Frecuencia del carácter lexicográficamente K-ésimo más pequeño en una string

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++ 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 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);
    }
}

# 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# 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.

<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)