💬 Discord
Sign In
NeetCode #52LC-2053EasyArrays & Hashing
← Back to All Problems

#52 · #2053 · Kth Distinct String in an Array(数组中第 K 个独一无二的字符串)

📌 Problem Statement & Constraints

A distinct string is one that appears exactly once in an array. Given an array of strings arr and an integer k, return the k-th distinct string present in arr in order of first appearance. If there are fewer than k distinct strings, return the empty string. Constraints: 1 <= k <= arr.length <= 1000.

💡 Core Algorithmic Approaches

  1. Count the frequency of every string with a hash map.
  2. Walk arr in order, and each time you encounter a string whose count is exactly 1, decrement k.
  3. When k reaches zero, return that string -- the walk order guarantees first-appearance order.
  4. If the walk finishes with k > 0, there are fewer than k distinct strings, so return the empty string.
  5. Iterating the map instead of the array would lose the order, which is the crux of the problem.

💻 Benchmark Python3 Implementation

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        from collections import Counter
        cnt = Counter(arr)
        for s in arr:                      # array order = first-appearance order
            if cnt[s] == 1:
                k -= 1
                if k == 0:
                    return s
        return ""

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count, one pass to find the k-th distinct string.
💾 Space Complexity
O(n) for the counter.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating the counter instead of the array: dict insertion order in Python happens to match first appearance, but relying on that is fragile and would break in other languages.
  • Not deduplicating the walk: a distinct string has count 1 by definition, so duplicates cannot appear -- but if you counted occurrences instead, you would overcount.
  • Returning None: the contract requires the empty string.
  • Sorting the distinct strings: the problem asks for first-appearance order, not lexicographic order.