Problem of The Day: Kth Distinct String in an Array

Problem Statement

Intuition

My first thought on solving this problem is to count the frequency of each string in the given array. By doing this, I can identify which strings are distinct (i.e., appear exactly once). Once I have this information, I can simply traverse the array again to find the k-th distinct string.

Approach

1. I will use a dictionary to keep track of the frequency of each string in the array.
2. Then, I will iterate through the array to build this frequency dictionary.
3. Next, I will traverse the array a second time and collect the distinct strings (those with a frequency of 1) in a temporary list.
4. As I collect these distinct strings, I will check if the length of the list equals k. If it does, I return the k-th distinct string.
5. If I reach the end of the array and have not found k distinct strings, I will return an empty string.

Complexity

• Time complexity:
  The time complexity is \(O(n)\) because I am making two passes over the array. The first pass is to build the frequency dictionary, and the second pass is to collect distinct strings and check their order.

• Space complexity:
  The space complexity is \(O(n)\) because I am using a dictionary to store the frequency of each string and a list to store the distinct strings.

Code

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        freq = defaultdict(int)
        temp = []

        # First pass: build the frequency dictionary
        for c in arr:
            freq[c] += 1

        # Second pass: collect distinct strings and find the k-th one
        for c in arr:
            if freq[c] == 1:
                temp.append(c)
            if len(temp) == k:
                return c

        # If there are less than k distinct strings, return an empty string
        return ""