Kth Distinct String in an Array

easy array hash map string counting

Problem

A distinct string is a string present only once in an array. Given an array arr of strings and an integer k, return the kth distinct string present in arr; if fewer than k distinct strings exist, return "".

Inputarr = ["d", "b", "c", "b", "c", "a"], k = 2

Output"a"

"d" and "a" appear once; the 2nd distinct one in order is "a".

arr (comma-separated)

def kth_distinct(arr, k):
    from collections import Counter
    cnt = Counter(arr)
    seen = 0
    for s in arr:
        if cnt[s] == 1:
            seen += 1
            if seen == k:
                return s
    return ""

function kthDistinct(arr, k) {
  const cnt = new Map();
  for (const s of arr) cnt.set(s, (cnt.get(s) || 0) + 1);
  let seen = 0;
  for (const s of arr) {
    if (cnt.get(s) === 1) {
      if (++seen === k) return s;
    }
  }
  return "";
}

class Solution {
    public String kthDistinct(String[] arr, int k) {
        Map<String, Integer> cnt = new HashMap<>();
        for (String s : arr) cnt.merge(s, 1, Integer::sum);
        int seen = 0;
        for (String s : arr) {
            if (cnt.get(s) == 1 && ++seen == k) return s;
        }
        return "";
    }
}

string kthDistinct(vector<string>& arr, int k) {
    unordered_map<string, int> cnt;
    for (auto& s : arr) cnt[s]++;
    int seen = 0;
    for (auto& s : arr) {
        if (cnt[s] == 1 && ++seen == k) return s;
    }
    return "";
}

Explanation

A string is distinct if it shows up exactly once in the array. We need the kth such distinct string, counting in the original order of the array — not sorted, not by first appearance of anything else.

The clean two-step idea: first count how many times every string appears, then walk the array a second time and pick out the distinct ones one by one until we reach the kth.

We build a frequency map with Counter(arr) so each string maps to its total count. Then we scan the array left to right; whenever cnt[s] == 1 the string is distinct, so we bump a running seen counter. The moment seen == k, that string is our answer.

Example: arr = ["d","b","c","b","c","a"], k = 2. Counts are d:1, b:2, c:2, a:1. Scanning, "d" is distinct (seen=1), then b and c repeat, then "a" is distinct (seen=2) — so we return "a".

If we finish the scan without reaching k, there are fewer than k distinct strings, so we return the empty string "".

Time: O(n) Space: O(n)