Sponsored
Sponsored
This approach involves using a dictionary (or hashmap) to count the frequency of each string in the array, and then iterating over the array once more to find the kth distinct string based on the order of appearance.
Time Complexity: O(n), where n is the number of strings in the array, because we make a single pass to record frequencies and another to find the kth distinct string.
Space Complexity: O(n), used for storing the frequency dictionary.
1def kthDistinct(arr, k):
2 frequency = {}
3 for string in arr:
4 frequency[string] = frequency.get(string, 0) + 1
5 distinct_count = 0
6 for string in arr:
7 if frequency[string] == 1:
8 distinct_count += 1
9 if distinct_count == k:
10 return string
11 return ""
12
13# Example usage
14arr = ["d","b","c","b","c","a"]
15k = 2
16print(kthDistinct(arr, k)) # Output: "a"First, we create a frequency map where each string maps to its count in the array. Then, we iterate over the array again, counting only those strings that appear once. The kth such string found during this iteration is returned. If fewer than k distinct strings are found, return an empty string.
This approach utilizes two passes over the array. In the first pass, we determine distinct elements using a count map. In the second pass, we filter using a set to collect exact distinct strings, maintaining their order.
Time Complexity: O(n).
Space Complexity: O(n), because of the hash map to store frequencies.
1function kthDistinct(arr, k) {
2
By creating an object to track frequencies of each string, we can easily check which elements are distinct through another pass. Once the kth distinct element is identified, it is returned.