Kth Distinct String in an Array — Problem & Solution
Kth Distinct String in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Kth Distinct String in an Array is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string of the array arr is distinct when it appears in arr exactly once.
Return the k-th distinct string, counting in the order the strings appear in arr (the first distinct string is the 1st). If arr has fewer than k distinct strings, return the empty string "".
Example 1
Input: arr = ["kai","ro","kai","duel","bug"], k = 2
Output: duel
Explanation: The distinct strings, in order, are `ro`, `duel`, `bug`.
Example 2
Input: arr = ["x","y","x","y"], k = 1
Output: ""
Explanation: No string appears exactly once, so the answer is the empty string.
Example 3
Input: arr = ["a","b","c"], k = 3
Output: c
Constraints
1 <= k <= arr.length <= 10001 <= arr[i].length <= 5arr[i] consists of lowercase English letters
Hints for Kth Distinct String in an Array
Hint 1
First find out how many times every string occurs.
Hint 2
A hash map from string to count does it in one pass.
Hint 3
Then walk
arrin order, counting downkon each string whose count is 1; the one that bringskto 0 is the answer.
How to solve Kth Distinct String in an Array
Two passes: count every string, then scan the array in its original order and pick the k-th string whose count is exactly one.
Approach
- Build a map
count[s]overarr. - Scan
arrfrom left to right; whenevercount[s] == 1, decrementk. - When
kreaches 0, return the current string. - If the scan ends first, return
"".
Why it works
The first pass gives the exact multiplicity of each string, so the second pass recognises distinct strings correctly; it visits them in array order, so the string at which the counter reaches zero is the k-th distinct one. A distinct string appears once, so it cannot be counted twice.
Complexity
- Time —
O(n · L) with L ≤ 5 - Space —
O(n · L)
Pitfalls
- "Distinct" means appearing exactly once, not "first occurrence of each value".
- Keep the original order — iterating the hash map would scramble it.
- Return the empty string, not null, when there are fewer than
kdistinct strings.
Reference solution
Python
from typing import List
from collections import Counter
def kthDistinct(arr: List[str], k: int) -> str:
cnt = Counter(arr)
for s in arr:
if cnt[s] == 1:
k -= 1
if k == 0:
return s
return ""Java
public static String kthDistinct(String[] arr, int k) {
Map<String, Integer> cnt = new HashMap<>();
for (String s : arr) cnt.merge(s, 1, Integer::sum);
for (String s : arr) {
if (cnt.get(s) == 1) {
k--;
if (k == 0) return s;
}
}
return "";
}C++
string kthDistinct(vector<string>& arr, int k) {
unordered_map<string, int> cnt;
for (const string& s : arr) cnt[s]++;
for (const string& s : arr) {
if (cnt[s] == 1) {
k--;
if (k == 0) return s;
}
}
return "";
}JavaScript
var kthDistinct = function(arr, k) {
var cnt = new Map();
for (var i = 0; i < arr.length; i++) cnt.set(arr[i], (cnt.get(arr[i]) || 0) + 1);
for (var j = 0; j < arr.length; j++) {
if (cnt.get(arr[j]) === 1) {
k--;
if (k === 0) return arr[j];
}
}
return "";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.