Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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

Author Riya
1 upvote
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Also read, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Previous article
Sort given Array using at most N cyclic shift on any subarray
Next article
How to sort and separate even and odd numbers in an array using a custom comparator?
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass