2053. Kth Distinct String in an Array - Explanation

Problem Link

1. Brute Force

Intuition

A string is distinct if it appears exactly once in the array. The simplest approach is to check each string against all other strings. For each position, we scan the entire array to see if that string appears anywhere else. If not, it's distinct, and we decrement our counter until we find the k-th one.

Algorithm

1. Iterate through each string at index i.
2. For each string, check all other positions j to see if there's a duplicate.
3. If no duplicate is found, the string is distinct; decrement k.
4. When k reaches 0, return the current string.
5. If we exhaust all strings without finding k distinct ones, return an empty string.

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        for i in range(len(arr)):
            flag = True
            for j in range(len(arr)):
                if i == j:
                    continue

                if arr[i] == arr[j]:
                    flag = False
                    break

            if flag:
                k -= 1
                if k == 0:
                    return arr[i]
        return ""

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(1)$

---

2. Hash Map

Intuition

Instead of repeatedly scanning the array, we can count occurrences upfront using a hash map. In the first pass, we count how many times each string appears. In the second pass, we iterate in order and check if each string has a count of exactly 1. This reduces time complexity from O(n^2) to O(n).

Algorithm

1. Create a hash map to count occurrences of each string.
2. Iterate through the array, incrementing the count for each string.
3. Iterate through the array again in order.
4. For each string with count equal to 1, decrement k.
5. Return the string when k becomes 0, or return an empty string if not found.

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        count = {}

        for s in arr:
            if s not in count:
                count[s] = 0
            count[s] += 1

        for s in arr:
            if count[s] == 1:
                k -= 1
                if k == 0:
                    return s

        return ""

Time & Space Complexity

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

---

3. Hash Set

Intuition

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.

Algorithm

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.

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 ""

Time & Space Complexity

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

---

Common Pitfalls

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.