Watch 10 video solutions for Kth Distinct String in an Array, a easy level problem involving Array, Hash Table, String. This walkthrough by NeetCodeIO has 6,972 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A distinct string is a string that is present only once in an array.
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 "".
Note that the strings are considered in the order in which they appear in the array.
Example 1:
Input: arr = ["d","b","c","b","c","a"], k = 2 Output: "a" Explanation: The only distinct strings in arr are "d" and "a". "d" appears 1st, so it is the 1st distinct string. "a" appears 2nd, so it is the 2nd distinct string. Since k == 2, "a" is returned.
Example 2:
Input: arr = ["aaa","aa","a"], k = 1 Output: "aaa" Explanation: All strings in arr are distinct, so the 1st string "aaa" is returned.
Example 3:
Input: arr = ["a","b","a"], k = 3 Output: "" Explanation: The only distinct string is "b". Since there are fewer than 3 distinct strings, we return an empty string "".
Constraints:
1 <= k <= arr.length <= 10001 <= arr[i].length <= 5arr[i] consists of lowercase English letters.Problem Overview: You receive an array of strings and an integer k. A string is considered distinct if it appears exactly once in the array. The task is to return the kth distinct string in the order it originally appears. If fewer than k distinct strings exist, return an empty string.
Approach 1: HashMap Count and Order of Appearance (O(n) time, O(n) space)
The most direct strategy is to count how many times each string appears, then scan the array again to preserve the original order. Use a hash map where the key is the string and the value is its frequency. First pass: iterate through the array and increment the count for each string. Second pass: iterate again and check if count[str] == 1. Each time you encounter such a string, decrement k. When k reaches zero, you found the answer. This approach works well because hash map lookups are O(1) on average, so both passes remain linear.
This method is common in problems involving frequency tracking with ordering constraints. The hash table stores counts efficiently, while the second traversal ensures the result respects the original array order. It is straightforward to implement and works in any language with dictionary support.
Approach 2: Two Pass Filtering with Set (O(n) time, O(n) space)
Another option separates the counting and filtering steps using a set-like structure. During the first pass, track frequencies using a map or maintain two sets: one for strings seen once and another for duplicates. When a string appears the first time, add it to the "seen once" set. When it appears again, move it to the duplicate set. After processing the array, only the elements that remained in the "seen once" set are distinct.
In the second pass, iterate through the original array again and check if the string belongs to the distinct set. Each time you encounter one, decrement k. When k == 0, return the string. This approach still runs in linear time and keeps logic clean by separating counting from ordering. It relies on constant-time membership checks provided by sets and maps, which are core features of array processing and string manipulation tasks.
Recommended for interviews: The hash map counting approach is the most expected solution. Interviewers want to see that you immediately recognize this as a frequency counting problem and use a HashMap or dictionary. The two-pass design demonstrates clarity: one pass to compute frequencies, another to maintain order. Brute force comparisons would be O(n²), which signals weaker problem decomposition, while the O(n) hash-based approach shows solid understanding of counting patterns in arrays.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Count and Order of Appearance | O(n) | O(n) | General case when you need frequency counting and must preserve original order |
| Two Pass Filtering with Set | O(n) | O(n) | Useful when separating duplicate tracking and distinct filtering improves readability |