Kth Distinct String in an Array

Difficulty: Easy | Acceptance: 82.10% | Paid: No Topics: Array, Hash Table, String, Counting

A distinct string is a string that is present only once in an array.

Given an array of strings arr, and an integer k, return the kth distinct string present in arr. If there are fewer than k distinct strings, return an empty string "".

• Examples
• Constraints
• Hash Map Frequency Count
• Brute Force Counting

Examples

Input: arr = ["d","b","c","b","c","a"], k = 2
Output: "a"
Explanation: 
The distinct strings in arr are "d" and "a". 
"d" appears first, so it is the 1st distinct string.
"a" appears second, so it is the 2nd distinct string.
The 2nd distinct string is "a".

Input: arr = ["aaa","aa","a"], k = 1
Output: "aa"
Explanation: 
The distinct strings in arr are "aa" and "a". 
"aa" appears first, so it is the 1st distinct string.
"a" appears second, so it is the 2nd distinct string.
Since k is 1, the 1st distinct string is "aa".

Input: arr = ["a","b","a"], k = 3
Output: ""
Explanation: 
The distinct strings in arr are "b". 
Since there is only 1 distinct string, the 3rd distinct string does not exist, so we return "".

Constraints

1 <= arr.length <= 1000
arr[i].length >= 1
arr[i] consists of lowercase English letters.
1 <= k <= 1000

Hash Map Frequency Count

Intuition Count the frequency of each string using a hash map, then iterate through the array to find the kth string with frequency 1.

Steps

• Build a frequency map of all strings in the array
• Iterate through the array in original order
• For each string, check if its frequency is 1 (distinct)
• When we find the kth distinct string, return it
• If we finish without finding k distinct strings, return ""

from collections import Counter
from typing import List

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        freq = Counter(arr)
        count = 0
        for s in arr:
            if freq[s] == 1:
                count += 1
                if count == k:
                    return s
        return ""

Complexity

• Time: O(n) where n is the length of arr
• Space: O(n) for the frequency map
• Notes: Optimal solution with linear time complexity

Brute Force Counting

Intuition For each string in the array, count its total occurrences by scanning the entire array. Track distinct strings and return the kth one.

Steps

• Iterate through each string in the array
• For each string, count its total occurrences in the array
• If the count is exactly 1, increment our distinct counter
• When the distinct counter reaches k, return that string
• If we finish the loop, return ""

from typing import List

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        count = 0
        for i, s in enumerate(arr):
            # Check if this is the first occurrence
            is_first = True
            for j in range(i):
                if arr[j] == s:
                    is_first = False
                    break
            if not is_first:
                continue
            
            # Count total occurrences
            total = 0
            for t in arr:
                if t == s:
                    total += 1
            
            if total == 1:
                count += 1
                if count == k:
                    return s
        return ""

Complexity

• Time: O(n²) where n is the length of arr
• Space: O(1) no extra space used
• Notes: Simpler implementation but quadratic time complexity, not recommended for large inputs