This blog will discuss the problem of finding the Kth lexicographically smallest distinct string from a given array of strings.

In this problem, we will be given an array containing ‘N’ strings and an integer ‘K’. We have to find the Kth lexicographically smallest distinct string from a given array of strings. If no such string exists, print an empty string.

The distinct strings, i.e the string occurring once in the array are: { "with", "coding", "ninjas"}

Here, the lexicographically second ( K=2) is “ninjas”.

So, we have to print “ninjas” (without quotes).

Now that we understand the problem let’s discuss the approach to solve it in the next section.

Solution Approach

This section will discuss the approach to find the Kth lexicographically smallest distinct string from a given array of strings. The approach to solve the problem is to first sort the array of strings in increasing order and then find the kth string, which occurs once in the array. We can use a ‘map’ with key as a string and value as its occurrence count to store the count of occurrences of each string in the array. Then traverse the map and find the kth string whose occurrence count is 1.

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:

arr - An array of strings

N - Size of the given array

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

What is a map? A map is a container to store data in the form of key-value pairs.

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.