Problem Description
Given an array of strings arr and an integer k, return the kth distinct string in the array. A string is distinct if it appears only once in the array. If there are fewer than k distinct strings, return an empty string. The order of distinct strings follows their original appearance in the array.
Key Insights
- Use a hash table to count the frequency of each string.
- A string is identified as distinct if its frequency equals one.
- Preserve the order in which strings appear to correctly identify the kth distinct string.
- Handle the edge case where the number of distinct strings is less than k.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the array, as it requires two passes over the array. Space Complexity: O(n), for storing the frequency count of each string in a hash table.
Solution
First, iterate over the array to build a frequency dictionary mapping each string to its count. Then, iterate again over the array and select the distinct strings (frequency equals one) in the same order they appear. Once the kth distinct string is encountered, return it. If the kth distinct string does not exist, return an empty string. The solution leverages a hash table (dictionary) to efficiently count frequencies and identify distinct elements.