1.
Introduction-
2.
Solution Approach
3.
Algorithm -
4.
C++ code:
5.
Algorithm Complexity:
6.
FAQs
7.
Key takeaways-
Last Updated: Mar 27, 2024

# Kth lexicographically smallest distinct String from given Array of Strings

Riya
1 upvote

## Introduction-

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.

Let’s understand the problem with an example:

Suppose,

N = 5,

arr = {"code", "code", "with", "coding", "ninjas"},

And, K = 2

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.

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

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

Live masterclass