Skip to main content
Talentd

Kth Distinct String in an Array - Solution & Explanation

EasyArrayHash TableStringCounting10 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive an array of strings and an integer k. A string is considered distinct if it appears exactly once in the array. The task is to return the kth distinct string in the order it originally appears. If fewer than k distinct strings exist, return an empty string.

Approach 1: HashMap Count and Order of Appearance (O(n) time, O(n) space)

The most direct strategy is to count how many times each string appears, then scan the array again to preserve the original order. Use a hash map where the key is the string and the value is its frequency. First pass: iterate through the array and increment the count for each string. Second pass: iterate again and check if count[str] == 1. Each time you encounter such a string, decrement k. When k reaches zero, you found the answer. This approach works well because hash map lookups are O(1) on average, so both passes remain linear.

This method is common in problems involving frequency tracking with ordering constraints. The hash table stores counts efficiently, while the second traversal ensures the result respects the original array order. It is straightforward to implement and works in any language with dictionary support.

Approach 2: Two Pass Filtering with Set (O(n) time, O(n) space)

Another option separates the counting and filtering steps using a set-like structure. During the first pass, track frequencies using a map or maintain two sets: one for strings seen once and another for duplicates. When a string appears the first time, add it to the "seen once" set. When it appears again, move it to the duplicate set. After processing the array, only the elements that remained in the "seen once" set are distinct.

In the second pass, iterate through the original array again and check if the string belongs to the distinct set. Each time you encounter one, decrement k. When k == 0, return the string. This approach still runs in linear time and keeps logic clean by separating counting from ordering. It relies on constant-time membership checks provided by sets and maps, which are core features of array processing and string manipulation tasks.

Recommended for interviews: The hash map counting approach is the most expected solution. Interviewers want to see that you immediately recognize this as a frequency counting problem and use a HashMap or dictionary. The two-pass design demonstrates clarity: one pass to compute frequencies, another to maintain order. Brute force comparisons would be O(nĀ²), which signals weaker problem decomposition, while the O(n) hash-based approach shows solid understanding of counting patterns in arrays.

Approach 1: Approach 1: HashMap Count and Order of Appearance

This approach involves using a dictionary (or hashmap) to count the frequency of each string in the array, and then iterating over the array once more to find the kth distinct string based on the order of appearance.

First, we create a frequency map where each string maps to its count in the array. Then, we iterate over the array again, counting only those strings that appear once. The kth such string found during this iteration is returned. If fewer than k distinct strings are found, return an empty string.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), where n is the number of strings in the array, because we make a single pass to record frequencies and another to find the kth distinct string.
Space Complexity: O(n), used for storing the frequency dictionary.

Try this approach in the editor ā†’

Approach 2: Approach 2: Two Pass Filtering with Set

This approach utilizes two passes over the array. In the first pass, we determine distinct elements using a count map. In the second pass, we filter using a set to collect exact distinct strings, maintaining their order.

The solution uses a hash map to count the occurrences of strings. In a second iteration, strings that appear only once are considered distinct. Counting these, when the kth distinct element is found, it is returned.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(n), because of the hash map to store frequencies.

Try this approach in the editor ā†’

Approach 3: Hash Table + Counting

We can use a hash table 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.

Time complexity is O(L), and space complexity is O(L), where L is the total length of all strings in the array arr.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Approach 1: HashMap Count and Order of Appearance

Time Complexity: O(n), where n is the number of strings in the array, because we make a single pass to record frequencies and another to find the kth distinct string.
Space Complexity: O(n), used for storing the frequency dictionary.

Approach 2: Two Pass Filtering with Set

Time Complexity: O(n).
Space Complexity: O(n), because of the hash map to store frequencies.

Hash Table + Countingā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap Count and Order of AppearanceO(n)O(n)General case when you need frequency counting and must preserve original order
Two Pass Filtering with SetO(n)O(n)Useful when separating duplicate tracking and distinct filtering improves readability

Video Solution

Kth Distinct String in an Array - Leetcode 2053 - Python ā€¢ NeetCodeIO ā€¢ 7,150 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Kth Distinct String in an Array easy or hard?
Kth Distinct String in an Array is categorized as an Easy problem. The main skill required is recognizing the frequency counting pattern with a hash map and preserving the original order of the array during the second pass.
Kth Distinct String in an Array Python/Java solution
In Python, use a dictionary or collections.Counter to track frequencies and iterate again to locate the kth string with count equal to one. In Java, use a HashMap<String, Integer> for counting and a second loop through the array. Both implementations run in O(n) time and O(n) space.
How to solve Kth Distinct String in an Array in O(n)?
Use a dictionary or hash map to store the frequency of each string during the first traversal of the array. Then iterate through the array again and check which strings have a count of exactly one. Decrease k whenever you encounter such a string and return the string when k reaches zero.
What is the best approach for Kth Distinct String in an Array?
The best approach uses a hash map to count how many times each string appears, followed by a second pass through the array to find the kth string with frequency equal to one. This preserves the original order while keeping lookups constant time. The total complexity is O(n) time and O(n) space.
Is Kth Distinct String in an Array asked at Google/Amazon/Meta?
Frequency counting and order-preserving array problems are common in interviews at companies like Amazon, Google, and Meta. While this exact problem may appear more often on coding platforms, the underlying hash map counting pattern is widely used in real interview questions.
What data structure is used in Kth Distinct String in an Array?
A hash map (or dictionary) is the primary data structure used to store string frequencies. Some implementations also use sets to track strings seen once versus duplicates. These structures provide constant-time insert and lookup operations.
What is the time complexity of Kth Distinct String in an Array?
The optimal solution runs in O(n) time where n is the number of strings. One pass counts frequencies using a hash map and a second pass identifies the kth distinct string. Hash map operations are O(1) on average, keeping the overall complexity linear.

Ready to solve this problem?

Practice Kth Distinct String in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Common Words With One Occurrence