Kth Distinct String in an Array

How it works

We can use two sets instead of a counting map. One set tracks strings that are currently distinct (seen exactly once), and another tracks strings we've already identified as duplicates. When we encounter a string, if it's in the distinct set, we move it to the seen set (it's no longer distinct). If it's not in either set, we add it to distinct. This achieves the same result with a slightly different data structure.

Steps

1. Create two sets: distinct for unique strings and seen for duplicates.
2. For each string in the array:
   • If it's in distinct, move it to seen (it's now a duplicate).
   • If it's not in seen, add it to distinct.
3. Iterate through the array again in order.
4. For strings in the distinct set, decrement k.
5. Return the string when k reaches 0.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Counting Distinct Strings Out of Order

The k-th distinct string must be found in the original array order, not in any arbitrary order. A common mistake is collecting all distinct strings into a set and then trying to find the k-th one, but sets do not preserve insertion order in all languages. Always iterate through the original array in order when finding the k-th distinct string.

Returning Before Finding the K-th Distinct String

If there are fewer than k distinct strings in the array, the function should return an empty string. Forgetting to handle this edge case or returning the last found distinct string instead of an empty string leads to incorrect results. Always check if k reaches zero before returning, and return empty string if the loop completes without finding enough distinct strings.

from typing import List

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        distinct, seen = set(), set()

        for s in arr:
            if s in distinct:
                distinct.remove(s)
                seen.add(s)
            elif s not in seen:
                distinct.add(s)

        for s in arr:
            if s in distinct:
                k -= 1
                if k == 0:
                    return s

        return ""

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        unordered_set<string> distinct, seen;

        for (const string& s : arr) {
            if (distinct.count(s)) {
                distinct.erase(s);
                seen.insert(s);
            } else if (!seen.count(s)) {
                distinct.insert(s);
            }
        }

        for (const string& s : arr) {
            if (distinct.count(s)) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }

        return "";
    }
};