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.
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.
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.
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.
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.
The solution uses a hash map to count the occurrences of strings. In a second iteration, strings that appear only once are considered distinct. Counting these, when the kth distinct element is found, it is returned.
Java
JavaScript
Time Complexity: O(n).
Space Complexity: O(n), because of the hash map to store frequencies.
We can use a hash table cnt to record the number of occurrences of each string. Then, we traverse the array once more. For each string, if its occurrence count is 1, we decrement k by one. When k reaches 0, we return the current string.
Time complexity is O(L), and space complexity is O(L), where L is the total length of all strings in the array arr.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: HashMap Count and 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. |
| Approach 2: Two Pass Filtering with Set | Time Complexity: O(n). |
| Hash Table + Counting | — |
| 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 |
Kth Distinct String in an Array - Leetcode 2053 - Python • NeetCodeIO • 6,972 views views
Watch 9 more video solutions →Practice Kth Distinct String in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor