LeetCode 2053: Kth Distinct String in an Array (Two Pass Frequency + Order Scan)
LeetCode 2053Hash TableStringToday we solve LeetCode 2053 - Kth Distinct String in an Array.
Source: https://leetcode.com/problems/kth-distinct-string-in-an-array/
English
Problem Summary
Given an array of strings arr and an integer k, return the k-th distinct string in arr in original order. A distinct string appears exactly once. If there are fewer than k distinct strings, return an empty string.
Key Insight
“Distinct” depends on global frequency, while “k-th” depends on original order. So we separate concerns: first count occurrences of every string, then scan the original array again and consume only strings with frequency 1.
Algorithm
- First pass: build a hash map freq where freq[s] is count of string s.
- Second pass: iterate arr in original order.
- If freq[s] == 1, decrement k.
- When k == 0, return current string.
- If traversal ends, return "".
Complexity Analysis
Let n be length of arr.
Time: O(n) average.
Space: O(n).
Common Pitfalls
- Using only a set and losing exact frequency info.
- Sorting distinct strings (breaks original order requirement).
- Forgetting to return empty string when not enough distinct strings exist.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String kthDistinct(String[] arr, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String s : arr) {
freq.put(s, freq.getOrDefault(s, 0) + 1);
}
for (String s : arr) {
if (freq.get(s) == 1) {
k--;
if (k == 0) {
return s;
}
}
}
return "";
}
}func kthDistinct(arr []string, k int) string {
freq := make(map[string]int)
for _, s := range arr {
freq[s]++
}
for _, s := range arr {
if freq[s] == 1 {
k--
if k == 0 {
return s
}
}
}
return ""
}class Solution {
public:
string kthDistinct(vector<string>& arr, int k) {
unordered_map<string, int> freq;
for (const string& s : arr) {
++freq[s];
}
for (const string& s : arr) {
if (freq[s] == 1) {
--k;
if (k == 0) return s;
}
}
return "";
}
};from collections import Counter
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
freq = Counter(arr)
for s in arr:
if freq[s] == 1:
k -= 1
if k == 0:
return s
return ""var kthDistinct = function(arr, k) {
const freq = new Map();
for (const s of arr) {
freq.set(s, (freq.get(s) || 0) + 1);
}
for (const s of arr) {
if (freq.get(s) === 1) {
k--;
if (k === 0) {
return s;
}
}
}
return "";
};中文
题目概述
给定字符串数组 arr 和整数 k，需要返回按原始顺序出现的第 k 个“不同字符串”。“不同字符串”定义为在数组中恰好出现一次。若不足 k 个，返回空字符串。
核心思路
“是否不同”取决于全局出现次数，而“第 k 个”取决于原始顺序，因此分两步处理最稳妥：先统计频次，再按原顺序筛选频次为 1 的字符串并计数。
算法步骤
- 第一遍遍历：用哈希表统计每个字符串出现次数。
- 第二遍遍历：按原顺序扫描数组。
- 若当前字符串频次为 1，就把 k 减一。
- 当 k == 0 时，当前字符串就是答案。
- 扫描结束仍未命中，返回 ""。
复杂度分析
设数组长度为 n。
时间复杂度：O(n)（平均）。
空间复杂度：O(n)。
常见陷阱
- 只用集合去重，丢失“出现次数是否等于 1”的关键信息。
- 对不同字符串排序后再取第 k 个，破坏了原顺序要求。
- 忘记在不足 k 个时返回空字符串。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String kthDistinct(String[] arr, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String s : arr) {
freq.put(s, freq.getOrDefault(s, 0) + 1);
}
for (String s : arr) {
if (freq.get(s) == 1) {
k--;
if (k == 0) {
return s;
}
}
}
return "";
}
}func kthDistinct(arr []string, k int) string {
freq := make(map[string]int)
for _, s := range arr {
freq[s]++
}
for _, s := range arr {
if freq[s] == 1 {
k--
if k == 0 {
return s
}
}
}
return ""
}class Solution {
public:
string kthDistinct(vector<string>& arr, int k) {
unordered_map<string, int> freq;
for (const string& s : arr) {
++freq[s];
}
for (const string& s : arr) {
if (freq[s] == 1) {
--k;
if (k == 0) return s;
}
}
return "";
}
};from collections import Counter
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
freq = Counter(arr)
for s in arr:
if freq[s] == 1:
k -= 1
if k == 0:
return s
return ""var kthDistinct = function(arr, k) {
const freq = new Map();
for (const s of arr) {
freq.set(s, (freq.get(s) || 0) + 1);
}
for (const s of arr) {
if (freq.get(s) === 1) {
k--;
if (k === 0) {
return s;
}
}
}
return "";
};
Comments