Kth Distinct String in an Array

Kth Distinct String in an Array

1. What is this problem about?

The Kth Distinct String in an Array interview question asks you to find the $k^{th}$ string in a list that appears exactly once. A string is "distinct" if its frequency in the entire array is 1. You should return the string that occupies the $k^{th}$ position among all distinct strings, in the order they appear in the original array.

2. Why is this asked in interviews?

Companies like Amazon and Bloomberg use this as a basic assessment of Hash Table interview patterns. It evaluations whether you can distinguish between "all unique elements" and "elements with a frequency of 1." It tests your ability to perform a two-pass linear scan efficiently.

3. Algorithmic pattern used

This problem follows the Frequency Counting pattern.

1. Pass 1: Iterate through the array and store the count of every string in a Hash Map.
2. Pass 2: Iterate through the original array again. For each string:
   • Check its count in the map.
   • If the count is exactly 1, it's a distinct string. Decrement $k$.
   • If $k$ reaches 0, you've found the $k^{th}$ distinct string.
3. Default: If the loop ends and $k > 0$, return an empty string.

4. Example explanation

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

1. Counts: a: 2, b: 1, c: 2, d: 1.
2. Second Pass:
   • "a": count 2 (skip).
   • "b": count 1 (distinct #1). $k$ becomes 1.
   • "a": count 2 (skip).
   • "c": count 2 (skip).
   • "c": count 2 (skip).
   • "d": count 1 (distinct #2). $k$ becomes 0. Found! Result: "d".

5. Common mistakes candidates make

• One-Pass attempt: Trying to find the $k^{th}$ distinct string in a single pass without knowing the total frequency of each string.
• Set vs Map: Using a simple Set, which only identifies if an element has been seen, but doesn't distinguish between appearing once vs. twice.
• Incorrect Order: Returning the $k^{th}$ distinct string based on alphabetical order instead of the order in the array.

6. Interview preparation tip

Always look for the "order of appearance" requirement. If it's required, you must either do a second pass over the original array or use an Ordered Hash Map (like LinkedHashMap in Java) to preserve insertion order.