Kth Distinct String in an Array

Let’s understand how to find the kth distinct string from the given array of strings, and then write code.

Approach

  1. Create a Counter: Use a dictionary to count the frequency of each string in the array.

  2. Find kth Distinct String: Iterate through the array, and for each string that appears only once, reduce the value of k. When k reaches 0, return the string at that position, as it is the kth distinct string.

  3. Handle Edge Cases: If there are fewer than k distinct strings, return an empty string "".

Example Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from collections import Counter

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        # Step 1: Create a counter
        string_count = Counter(arr)

        # Step 2: Find kth Distinct String
        for string in arr:
            if string_count[string] == 1:
                k -= 1
                if k == 0:
                    return string

        # Step 3: Handle Edge Cases
        return ""

Explanation

  • For arr = ["d","b","c","b","c","a"] and k = 2, the counter will be {'d': 1, 'b': 2, 'c': 2, 'a': 1}.
  • When iterating through the array, the first distinct string is “d” and the second distinct string is “a”. Since k = 2, we return “a”.

Key Takeaways

  • The solution counts the frequency of each string and then iterates through the array to find the kth distinct string.
  • It ensures to handle the case where there are fewer than k distinct strings by returning an empty string.
  • This approach is simple and adheres to the problem constraints, considering strings in the order they appear in the array.