Problem Description
Given an array of strings arr, and an integer k, return the kth distinct string present in arr. If there are fewer than k distinct strings, return an empty string "". The strings are considered in the order in which they appear in the array.
Key Insights
- A distinct string is defined as a string that appears only once in the array.
- The order of appearance in the array is crucial for determining the k-th distinct string.
- We can utilize a hash table (dictionary) to count occurrences of each string, which allows us to efficiently identify distinct strings.
- After counting, we can iterate through the array again to collect distinct strings in the correct order.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the array arr. We traverse the array a constant number of times (twice in total).
Space Complexity: O(m), where m is the number of unique strings in arr. This is the space required to store the counts of each string.
Solution
To solve this problem, we will use a hash table (dictionary) to count the occurrences of each string in the array. After counting, we will iterate through the array a second time to collect the distinct strings (those that have a count of 1). Finally, we will check if we have enough distinct strings to return the k-th one.