#2053

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Kth Distinct String in an Array

Find the kth distinct string in an array by identifying strings that appear only once, using efficient array scanning and hash lookup.

array hash table string counting

Problem Statement

Given an array of strings arr and an integer k, your task is to return the kth distinct string present in the array. A distinct string is one that appears exactly once in the array, and the order of strings matters as they appear.

If there are fewer than k distinct strings in the array, return an empty string. The problem emphasizes using array scanning along with hash table lookups to efficiently track distinct strings and their occurrences.

Examples

Example 1

Input: arr = ["d","b","c","b","c","a"], k = 2

Output: "a"

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"

All strings in arr are distinct, so the 1st string "aaa" is returned.

Example 3

Input: arr = ["a","b","a"], k = 3

Output: ""

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 Approach

Array Scanning with Hash Map

Iterate through the array while using a hash map to count the occurrences of each string. As you identify distinct strings (count equals 1), keep track of their order. When k distinct strings have been found, return the kth one.

Early Exit on k Distinct Strings

To avoid unnecessary operations, stop scanning the array as soon as k distinct strings are found. This reduces runtime and ensures you don’t process elements once the result is determined.

Handle Edge Cases

Consider edge cases like arrays with fewer than k distinct strings or arrays where all elements are duplicates. Ensure the solution returns an empty string if there are not enough distinct strings.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because the array is scanned once, and each string lookup or insertion in the hash map takes constant time, O(1). The space complexity is O(n) due to the storage required for the hash map to track string occurrences.

What Interviewers Usually Probe

Check for familiarity with hash maps and array scanning.
Verify the candidate's understanding of distinct elements and efficient lookups.
Evaluate their approach to handling edge cases, especially with fewer distinct strings.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding what counts as a distinct string; strings must appear only once in the array.
Failing to handle the case where fewer than k distinct strings exist, leading to incorrect results.
Not efficiently using a hash map or failing to terminate the scan early when k distinct strings are found.

Follow-up variants

Return the first distinct string instead of the kth one.
Modify the function to return the kth most frequent distinct string.
Handle larger arrays with optimized space and time complexities, exploring advanced hashing techniques.

FAQ

What is the time complexity of solving the Kth Distinct String in an Array?

The time complexity is O(n), where n is the length of the array. The array is scanned once, and each string lookup or insertion in the hash map takes constant time.

What should I do if there are fewer than `k` distinct strings in the array?

If there are fewer than k distinct strings, the solution should return an empty string, as there is no kth distinct string.

What’s the main pattern used to solve the Kth Distinct String in an Array problem?

The main pattern is array scanning combined with hash map lookups. This allows you to efficiently track distinct strings and return the kth one when found.

How do I handle duplicate strings in the Kth Distinct String in an Array?

Duplicates are ignored when identifying distinct strings. Only strings that appear exactly once are considered distinct.

What are the space complexity and how do they affect the solution?

The space complexity is O(n), where n is the number of strings in the array. This is due to the need for storing the count of each string in a hash map.

terminal

Solution

Solution 1: Hash Table + Counting

We can use a hash table $\textit{cnt}$ to record the number of occurrences of each string. Then, we traverse the array once more. For each string, if its occurrence count is $1$, we decrement $k$ by one. When $k$ reaches $0$, we return the current string.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2023 number of pairs of strings with concatenation equal to target #2085 count common words with one occurrence #2131 longest palindrome by concatenating two letter words