LeetCode 2053 - Kth Distinct String in an Array

LeetCode Problem 2053

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to find the kth distinct string in an array of strings. A string is considered distinct if it appears exactly once in the entire array.

The important detail is that the order matters. We are not sorting the strings or rearranging them in any way. Instead, we must consider distinct strings in the same order they originally appear in the array.

For example, if the array is:

["d","b","c","b","c","a"]

then:

• "d" appears once, so it is distinct
• "b" appears twice, so it is not distinct
• "c" appears twice, so it is not distinct
• "a" appears once, so it is distinct

The distinct strings, in order, are:

["d", "a"]

If k = 2, the answer is "a".

The input consists of:

• arr, an array of lowercase strings
• k, a positive integer

The output should be:

• the kth distinct string in appearance order
• or an empty string "" if fewer than k distinct strings exist

The constraints are relatively small:

• arr.length <= 1000
• each string length is at most 5

These constraints mean even a quadratic solution would technically pass, but we should still aim for a clean and efficient approach.

Several edge cases are important:

• Arrays where no strings are distinct
• Arrays where every string is distinct
• Cases where k is larger than the number of distinct strings
• Repeated strings appearing many times
• Very small arrays, including length 1

A correct solution must preserve original order while accurately counting occurrences.

Approaches

Brute Force Approach

The brute-force method checks every string individually and counts how many times it appears in the array.

For each string:

1. Scan the entire array again
2. Count occurrences
3. If the count is exactly 1, it is distinct
4. Keep track of how many distinct strings have been found
5. Return the kth one

This approach is correct because it explicitly verifies the occurrence count for every string. However, it repeatedly scans the array for each element, which is inefficient.

If the array has n elements, and each element requires another full scan of n, the total time complexity becomes O(n²).

Although n <= 1000 is small enough for this to pass, it is unnecessary work.

Optimal Approach

The key observation is that we repeatedly compute the same frequency counts.

Instead of recounting each string many times, we can count all occurrences once using a hash map.

The algorithm works in two passes:

1. First pass:

• Count how many times each string appears

2. Second pass:

• Iterate through the original array in order
• Select only strings with frequency 1
• Return the kth such string

A hash map is ideal here because it provides average O(1) lookup and insertion time.

This reduces the overall time complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recounts occurrences for every string
Optimal	O(n)	O(n)	Uses a hash map for frequency counting

Algorithm Walkthrough

Optimal Algorithm

1. Create a hash map called frequency.

This map stores how many times each string appears in the array. The key is the string, and the value is its occurrence count. 2. Traverse the array once to build frequencies.

For every string s in arr:

• Increment frequency[s]

After this step, we know exactly how many times every string appears. 3. Traverse the array again in original order.

We must preserve the order of appearance, so we iterate through arr exactly as given. 4. Check whether the current string is distinct.

A string is distinct if:

frequency[s] == 1

5. Count distinct strings as they appear.

Each time we find a distinct string:

• Decrement k

6. Return the answer when k == 0.

Once we have encountered the kth distinct string, return it immediately. 7. If the traversal finishes without finding enough distinct strings, return "".

Why it works

The frequency map guarantees that we correctly identify whether a string is distinct. The second traversal preserves the original ordering required by the problem. Since we decrement k only when encountering distinct strings, the moment k reaches zero corresponds exactly to the kth distinct string in order.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        frequency = Counter(arr)

        for string in arr:
            if frequency[string] == 1:
                k -= 1

                if k == 0:
                    return string

        return ""

The implementation begins by using Counter from Python's collections module. This automatically computes the frequency of every string in the array.

frequency = Counter(arr)

For example:

Counter({
    "b": 2,
    "c": 2,
    "d": 1,
    "a": 1
})

Next, we iterate through the array in its original order.

for string in arr:

For each string, we check whether its frequency is exactly 1.

if frequency[string] == 1:

If it is distinct, we decrement k.

k -= 1

When k becomes zero, we have reached the kth distinct string.

if k == 0:
    return string

If the loop finishes without returning, there are fewer than k distinct strings, so we return an empty string.

return ""

Go Solution

func kthDistinct(arr []string, k int) string {
    frequency := make(map[string]int)

    for _, str := range arr {
        frequency[str]++
    }

    for _, str := range arr {
        if frequency[str] == 1 {
            k--

            if k == 0 {
                return str
            }
        }
    }

    return ""
}

The Go solution follows exactly the same logic as the Python implementation.

A map[string]int is used to store frequencies.

frequency := make(map[string]int)

The first loop counts occurrences.

frequency[str]++

The second loop preserves original order and identifies distinct strings.

Go strings are immutable and comparable, so they work naturally as hash map keys.

Unlike Python, Go does not have a built-in Counter, so we manually increment counts.

Returning "" is straightforward because an empty string is the zero value for strings in Go.

Worked Examples

Example 1

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

Step 1, Build Frequency Map

String	Count
d	1
b	2
c	2
a	1

Step 2, Traverse in Order

Index	String	Frequency	Distinct?	k After Processing
0	d	1	Yes	1
1	b	2	No	1
2	c	2	No	1
3	b	2	No	1
4	c	2	No	1
5	a	1	Yes	0

When k becomes 0, return "a".

Example 2

Input:
arr = ["aaa","aa","a"]
k = 1

Frequency Map

String	Count
aaa	1
aa	1
a	1

Traversal

Index	String	Frequency	Distinct?	k After Processing
0	aaa	1	Yes	0

Return "aaa" immediately.

Example 3

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

Frequency Map

String	Count
a	2
b	1

Traversal

Index	String	Frequency	Distinct?	k After Processing
0	a	2	No	3
1	b	1	Yes	2
2	a	2	No	2

The traversal ends before k reaches 0, so return:

""

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count frequencies and one pass to find the answer
Space	O(n)	Hash map may store all unique strings

The algorithm performs two linear scans of the array. Hash map operations are average O(1), so the total runtime remains linear.

The extra space comes from storing frequencies of distinct strings. In the worst case, every string is unique, requiring O(n) additional space.

Test Cases

solution = Solution()

# Provided examples
assert solution.kthDistinct(["d","b","c","b","c","a"], 2) == "a"  # second distinct string
assert solution.kthDistinct(["aaa","aa","a"], 1) == "aaa"  # all strings distinct
assert solution.kthDistinct(["a","b","a"], 3) == ""  # fewer than k distinct strings

# Single element array
assert solution.kthDistinct(["x"], 1) == "x"  # smallest valid input

# No distinct strings
assert solution.kthDistinct(["a","a","b","b"], 1) == ""  # all repeated

# Exactly one distinct string
assert solution.kthDistinct(["a","b","a"], 1) == "b"  # only one distinct value

# Distinct strings appear later
assert solution.kthDistinct(["x","x","y","z"], 2) == "z"  # second distinct near end

# k equals number of distinct strings
assert solution.kthDistinct(["a","b","c"], 3) == "c"  # last distinct string

# Repeated strings many times
assert solution.kthDistinct(["a","a","a","b","c","c"], 1) == "b"  # one unique among many duplicates

# Multiple distinct strings
assert solution.kthDistinct(["p","q","r","p","s"], 3) == "s"  # third distinct string

# k larger than distinct count
assert solution.kthDistinct(["a","b","b"], 2) == ""  # only one distinct string exists

Test	Why
["d","b","c","b","c","a"], k=2	Validates normal mixed case
["aaa","aa","a"], k=1	Validates all unique strings
["a","b","a"], k=3	Validates insufficient distinct strings
["x"], k=1	Smallest possible input
["a","a","b","b"], k=1	Validates no distinct strings
["a","b","a"], k=1	Validates exactly one distinct string
["x","x","y","z"], k=2	Ensures order is preserved
["a","b","c"], k=3	Validates last distinct element
["a","a","a","b","c","c"], k=1	Handles many duplicates
["p","q","r","p","s"], k=3	Validates counting multiple distinct strings
["a","b","b"], k=2	Validates k exceeding distinct count

Edge Cases

Case 1, No Distinct Strings

Consider:

["a", "a", "b", "b"]

Every string appears more than once. A buggy implementation might incorrectly return the first element or fail to handle the absence of valid answers.

Our implementation correctly checks:

frequency[string] == 1

Since no string satisfies this condition, the loop completes and returns "".

Case 2, All Strings Are Distinct

Consider:

["x", "y", "z"]

Every string appears exactly once. This tests whether the algorithm preserves original order correctly.

Our implementation processes the array sequentially and decrements k each time a distinct string is found, so the order remains accurate.

Case 3, k Larger Than the Number of Distinct Strings

Consider:

["a", "b", "a"]
k = 5

There is only one distinct string, "b".

A careless implementation might access invalid indices or assume the answer always exists.

Our algorithm safely traverses the entire array. If k never reaches 0, it returns an empty string at the end.

Case 4, Distinct String Appears Late

Consider:

["x", "x", "x", "y"]

The only distinct string appears at the very end.

This validates that the algorithm continues scanning the entire array and does not stop early when duplicates dominate the beginning.

Because we perform a complete second pass through the array, the implementation correctly identifies "y" as the answer.