K-ésima String distinta lexicográficamente más pequeña de una array de strings dada

Dada una array arr que tiene N strings y un número entero K , la tarea es encontrar la K-ésima string distinta lexicográficamente más pequeña . Imprime una string vacía si no existe tal string.

Ejemplo:

Entrada: arr[]={“aa”, “aa”, “bb”, “cc”, “dd”, “cc”}, K = 2
Salida: dd
Explicación: Las distintas strings son: “bb”, “dd ”. La segunda string más pequeña entre estas es «dd»

Entrada: arr[]={“aa”, “aa”, “bb”, “cc”, “dd”, “cc”}, K = 1
Salida: bb

Enfoque: el problema dado se puede resolver clasificando primero la array de strings dada y luego imprimiendo la K-ésima string con frecuencia 1. Siga los pasos a continuación para resolver este problema:

1. Ordenar la array dada de strings
2. Cree un mapa para almacenar la frecuencia de cada string.
3. Ahora, recorra el mapa y reduzca el valor de K cada vez que encuentre una string que tenga una frecuencia de uno.
4. Cuando K se vuelve cero, imprime la siguiente string que tiene una frecuencia de 1.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print lexicographically
// smallest Kth string
string KthDistinctString(vector<string>& arr, int K)
{
 
    // Sorting the array of strings
    sort(arr.begin(), arr.end());
 
    // Map to store the strings
    map<string, int> mp;
    for (auto x : arr) {
        mp[x]++;
    }
 
    for (auto x : mp) {
 
        // Reducing K
        if (x.second == 1) {
            K--;
        }
 
        if (K == 0 and x.second == 1) {
            return x.first;
        }
    }
 
    return "";
}
 
// Driver Code
int main()
{
    vector<string> a
        = { "aa", "aa", "bb", "cc", "dd", "cc" };
    int K = 2;
    cout << KthDistinctString(a, K);
}

// Java code for the above approach
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
 
class GFG {
 
    // Function to print lexicographically
    // smallest Kth string
    static String KthDistinctString(ArrayList<String> arr, int K) {
 
        // Sorting the array of strings
        Collections.sort(arr);
 
        // Map to store the strings
        HashMap<String, Integer> mp = new HashMap<String, Integer>();
 
        for (String x : arr) {
            int count = 0;
 
            if (mp.containsKey(x)) {
                count = mp.get(x);
            }
            mp.put(x, count + 1);
        }
 
        for (String x : mp.keySet()) {
            // Reducing K
            if (mp.get(x) == 1) {
                K--;
            }
 
            if (K == 0 && mp.get(x) == 1) {
                return x;
            }
        }
 
        return "";
    }
 
    // Driver Code
    public static void main(String args[]) {
        ArrayList<String> a = new ArrayList<String>();
 
        a.add("aa");
        a.add("aa");
        a.add("bb");
        a.add("cc");
        a.add("dd");
        a.add("cc");
 
        int K = 2;
        System.out.println(KthDistinctString(a, K));
    }
}
 
// This code is contributed by gfgking

# Python3 code for the above approach
 
# Function to print lexicographically
# smallest Kth string
def KthDistinctString(arr, K):
     
    # Sorting the array of strings
    arr.sort()
 
    # Map to store the strings
    mp = {}
    for x in arr:
        if x in mp:
            mp[x] += 1
        else:
            mp[x] = 1
 
    for x in mp:
 
        # Reducing K
        if (mp[x] == 1):
            K -= 1
 
        if (K == 0 and mp[x] == 1):
            return x
 
    return ""
 
# Driver Code
if __name__ == "__main__":
 
    a = [ "aa", "aa", "bb", "cc", "dd", "cc" ]
    K = 2
     
    print(KthDistinctString(a, K))
 
# This code is contributed by rakeshsahni

// C# code for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
   
// Function to print lexicographically
// smallest Kth string
static string KthDistinctString(ArrayList arr, int K)
{
 
    // Sorting the array of strings
    arr.Sort();
 
    // Map to store the strings
    Dictionary<string, int> mp =
          new Dictionary<string, int>();
           
    foreach (string x in arr) {
        int count = 0;
         
        if (mp.ContainsKey(x)) {
                count = mp[x];
        }
        mp[x] = count + 1;
    }
 
    foreach (KeyValuePair<string, int> x in mp) {
        // Reducing K
        if (x.Value == 1) {
            K--;
        }
 
        if (K == 0 && x.Value == 1) {
            return x.Key;
        }
    }
 
    return "";
}
 
// Driver Code
public static void Main()
{
    ArrayList a = new ArrayList();
     
    a.Add("aa");
    a.Add("aa");
    a.Add("bb");
    a.Add("cc");
    a.Add("dd");
    a.Add("cc");
     
    int K = 2;
    Console.Write(KthDistinctString(a, K));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
       // JavaScript Program to implement
       // the above approach
 
       // Function to print lexicographically
       // smallest Kth string
       function KthDistinctString(arr, K) {
 
           // Sorting the array of strings
           arr.sort();
 
           // Map to store the strings
           let mp = new Map();
           for (let x of arr) {
               if (mp.has(x))
                   mp.set(x, mp.get(x) + 1);
               else
                   mp.set(x, 1);
 
           }
 
           for (let [key, value] of mp)
           {
 
               // Reducing K
               if (value == 1) {
                   K--;
               }
 
               if (K == 0 && value == 1) {
                   return key;
               }
           }
 
           return "";
       }
 
       // Driver Code
       let a
           = ["aa", "aa", "bb", "cc", "dd", "cc"];
       let K = 2;
       document.write(KthDistinctString(a, K));
 
   // This code is contributed by Potta Lokesh
   </script>

dd

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)