Kth lexicographically smallest distinct String from given Array of Strings

Algorithm -

Step 1. Create a function “KthSmallestDistinctString()” to find the Kth lexicographically smallest distinct string from a given array of strings. It takes the following inputs:

1. arr - An array of strings
2. N - Size of the given array
3. K - We have to find the kth smallest distinct string

Step 2. Inside the function “KthSmallestDistinctString()” , first sort the given array. Then create a map to store the count of occurrences of each string.

Step 3. Now, traverse each entry of the map and if the occurrence count of the string is 1, then reduce the value of K.

Step 4. Finally, when the value of k becomes zero and we find a string with the occurrence count 1, then return that string.

C++ code:

// C++ code to find Kth lexicographically smallest distinct string from a given array of strings
#include <bits/stdc++.h>
using namespace std;


// Function to return Kth lexicographically smallest distinct string from a given array of strings
string KthSmallestDistinctString(string arr[], int N, int K)
{


// Sort the given array of strings
sort(arr, arr+N);


// Map to store count of strings
map<string, int> count;

for (int i=0; i<N; i++) 
{
count[arr[i]]++;
}


for (auto x : count) 
{
    
             // Reduce K if the count of string is equal to 1
if (x.second == 1) 
{
K--;
}


if (K == 0 and x.second == 1) 
{
return x.first;
}
}


       // If a string with given condition doesn't exist, returning an empty string
return "";
}


// Main function
int main()
{
string arr[5] = {"code", "code", "with", "coding", "ninjas"};
int N = sizeof(arr)/sizeof(string);
int K = 2;

// Calling the function to find Kth lexicographically smallest distinct string from a given array of strings
cout << KthSmallestDistinctString(arr, N, K);
}

Output:
ninjas

Algorithm Complexity: 

Time Complexity: O(N * log(N))

In the function “KthSmallestDistinctString()”, we have used the sorting function to sort the given array, which takes O(N*log(N)) time. Also, we have created a map, and inserting one element in the map takes O(log N) time. So, the overall time complexity is O(N*log(N)), where ‘N’ is the number of strings in the given array.

Space Complexity: O(N) 

In the function “KthSmallestDistinctString()”, we have created a map to store the count of occurrences of the strings. So, the space complexity is O(N), where ‘N’ is the number of strings in the given array.

FAQs

1. What is a map?
   A map is a container to store data in the form of key-value pairs.
    
2. What is the time complexity of inserting an element in a map in C++?
   The time complexity to insert an element into a map in C++ is O(logN) where ‘N’ is the number of elements in the map.

Key takeaways-

This article discussed the problem “Kth lexicographically smallest distinct string from a given array of strings”, the solution approach to this problem,  its C++ implementation, and its time and space complexity.

If you want to solve similar problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

Check out this problem - Multiply Strings

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.