Kth Distinct String in an Array

Leetcode Problem:

• Kth Distinct String in an Array

Summary

• Given an array of strings and an integer k, return the kth distinct string present in the array
• If there are fewer than k distinct strings, return an empty string.

Approach

• The approach used is to count the frequency of each string in the array using an unordered map
• Then, iterate through the array again to find the kth distinct string
• If k is greater than the number of distinct strings, return an empty string.

Complexity

• O(n + m) where n is the size of the array and m is the number of distinct strings

Explain

• First, we create an unordered map to store the frequency of each string in the array
• We then initialize a counter K to keep track of the number of distinct strings
• We iterate through the array again, and for each string, we check if its frequency is 1
• If it is, we increment the counter K
• If K equals k, we return the current string
• If we finish iterating through the array and K is still less than k, we return an empty string.

Solution Code:

class Solution {
public:
    string kthDistinct(vector& arr, int k) {
        unordered_map m;
        for(int i = 0 ; i < arr.size(); i++){
            m[arr[i]]++;
        }
        int K = 0;
        for(int i = 0 ; i < arr.size(); i++){
            if(m[arr[i]] == 1){
                K++;
                if(k == K) return arr[i];
            }
        }
        return "";
    }
};