Kth Distinct String In An Array - Leetcode Solution

Problem Statement: Given an array of strings strs and an integer k. Return the kth non-repeating string in strs. If there are multiple answers return the first one.

Example: Input: strs = ["a","b","c","a","b","c"], k = 3 Output: "c" Explanation: The non-repeating strings are ["a","b","c"] and among them "c" is the third one.

Solution: There are multiple ways to approach this problem but we will discuss the most optimal one here which has a time complexity of O(n).

Step 1: Create a dictionary to store the frequency of each string in the array. The key will be the string and the value will be its count in the array.

Step 2: Create a list of non-repeating strings. Loop through the dictionary and add all the strings with a count of 1 to this list.

Step 3: Sort this list in lexicographical order.

Step 4: Return the kth element of this list. If the list is shorter than k, return an empty string.

Code:

def kthDistinct(strs, k):
    freq = {}
    for s in strs:
        freq[s] = freq.get(s, 0) + 1
    
    non_repeating = []
    for s in freq:
        if freq[s] == 1:
            non_repeating.append(s)
    
    sorted_list = sorted(non_repeating)
    
    return sorted_list[k-1] if len(sorted_list) >= k else ''

Explanation: We first create a dictionary to store the frequency of each string in the array. We use the get() method to add a default value of 0 to the count of a string key that does not exist in the dictionary.

freq = {}
for s in strs:
    freq[s] = freq.get(s, 0) + 1

We then loop through the dictionary and add all the strings with a count of 1 to a list of non-repeating strings.

non_repeating = []
for s in freq:
    if freq[s] == 1:
        non_repeating.append(s)

We sort this list in lexicographical order.

sorted_list = sorted(non_repeating)

Finally, we return the kth element of this list if it exists or an empty string if the list is shorter than k.

return sorted_list[k-1] if len(sorted_list) >= k else ''

This approach has a time complexity of O(n) as we loop through the array and the dictionary only once each. The space complexity is also O(n) as we store the frequency of each string in the dictionary and the non-repeating strings in the list.

1