{x}
blog image

Kth Distinct String in an Array

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

Note that the strings are considered in the order in which they appear in the array.

 

Example 1:

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

Example 2:

Input: arr = ["aaa","aa","a"], k = 1
Output: "aaa"
Explanation:
All strings in arr are distinct, so the 1st string "aaa" is returned.

Example 3:

Input: arr = ["a","b","a"], k = 3
Output: ""
Explanation:
The only distinct string is "b". Since there are fewer than 3 distinct strings, we return an empty string "".

 

Constraints:

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

Solution Explanation: Finding the Kth Distinct String

The problem asks to find the kth distinct string in an array, considering the order of appearance. A distinct string is one that appears only once in the array. If fewer than k distinct strings exist, an empty string should be returned.

Approach: Hash Table and Counting

The most efficient approach leverages a hash table (or dictionary in Python) to count the occurrences of each string. This allows for quick lookups of string frequencies.

Algorithm:

  1. Count Occurrences: Iterate through the input array arr. For each string, use a hash table (cnt) to store its count. If a string is already in cnt, increment its count; otherwise, add it with a count of 1.

  2. Find Kth Distinct String: Iterate through arr again. For each string:

    • Check its count in cnt. If the count is 1 (meaning it's distinct):
      • Decrement k.
      • If k becomes 0, this is the kth distinct string; return it.

  3. Return Empty String: If the loop completes without finding the kth distinct string, it means fewer than k distinct strings exist. Return an empty string.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the length of the input array arr. We iterate through the array twice in the worst case (once for counting and once for finding the kth distinct string). The hash table operations (insertion and lookup) are typically O(1) on average.

  • Space Complexity: O(M), where M is the number of unique strings in the array. In the worst case, the hash table cnt might store all unique strings. This space complexity can be at most O(N) if all strings are unique.

Code Implementation (Python)

from collections import Counter
 
class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        cnt = Counter(arr)  #Efficiently counts string occurrences
        for s in arr:
            if cnt[s] == 1:
                k -= 1
                if k == 0:
                    return s
        return ""

This Python code uses the Counter class from the collections module for efficient counting, making the code concise and readable. Other languages offer similar efficient data structures (like HashMap in Java, C++, Go, JavaScript, and Map in TypeScript, HashMap in Rust).

Code Implementation (Java)

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public String kthDistinct(String[] arr, int k) {
        Map<String, Integer> cnt = new HashMap<>();
        for (String s : arr) {
            cnt.put(s, cnt.getOrDefault(s, 0) + 1);
        }
        for (String s : arr) {
            if (cnt.get(s) == 1) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }
        return "";
    }
}

The Java code utilizes a HashMap for efficient string counting and lookup. The getOrDefault method simplifies handling cases where a string is not yet in the map. Similar approaches are used in other languages shown previously.