Kth Distinct String in an Array solution and explanation
Google
9 more videos on this problem
Kth Distinct String in an Array - Leetcode 2053 - PythonNeetCodeIO · 8:21 · 7K views
2053 Kth Distinct String in an Array | Daily Leetcode Challange | HashMap | Java SolutionCakot Coding · 6:54 · 1K views
2053. Kth Distinct String in an Array (Leetcode Easy)Programming Live with Larry · 3:05 · 466 views
2053 Kth Distinct String in an Array || Leetcode || HashMapCoding Guys · 11:43 · 334 views
2053. Kth Distinct String in an Array II Dry Runs | Leetcode| JAVA | C++ || BrogrammersBrogrammers · 17:35 · 320 views
2053. Kth Distinct String in an Array | Zero to FAANG | Shapnesh | LeetcodeProgrammers Zone · 8:01 · 238 views
Kth Distinct String in an Array - Leetcode 2053 - JavaCode With K5KC · 9:21 · 189 views
LeetCode #2053: Kth Distinct String in an Array | LeetCode DailyAnish · 8:39 · 180 views
LeetCode 2053 - Kth Distinct String in An Array - JavaAlpha-Code · 3:54 · 117 views
Leetcode 2053 Kth Distinct String in an Array - Python SolutionData Engineering Studies · 5:01 · 88 views
The problem
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 <= 10001 <= arr[i].length <= 5arr[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.
def kthDistinct(arr, k):
frequency = {}
for string in arr:
frequency[string] = frequency.get(string, 0) + 1
distinct_count = 0
for string in arr:
if frequency[string] == 1:
distinct_count += 1
if distinct_count == k:
return string
return ""
# Example usage
arr = ["d","b","c","b","c","a"]
k = 2
print(kthDistinct(arr, k)) # Output: "a"#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
string kthDistinct(vector<string>& arr, int k) {
unordered_map<string, int> frequency;
for (const string& str : arr) {
frequency[str]++;
}
int distinct_count = 0;
for (const string& str : arr) {
if (frequency[str] == 1) {
distinct_count++;
if (distinct_count == k) {
return str;
}
}
}
return "";
}
// Example usage
int main() {
vector<string> arr = {"d","b","c","b","c","a"};
int k = 2;
cout << kthDistinct(arr, k) << endl; // Output: "a"
return 0;
}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.
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: 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.
import java.util.*;
public class KthDistinctString {
public static String kthDistinct(String[] arr, int k) {
Map<String, Integer> frequency = new HashMap<>();
for (String str : arr) {
frequency.put(str, frequency.getOrDefault(str, 0) + 1);
}
int distinct_count = 0;
for (String str : arr) {
if (frequency.get(str) == 1) {
distinct_count++;
if (distinct_count == k) {
return str;
}
}
}
return "";
}
public static void main(String[] args) {
String[] arr = {"d","b","c","b","c","a"};
int k = 2;
System.out.println(kthDistinct(arr, k)); // Output: "a"
}
}function kthDistinct(arr, k) {
const frequency = {};
for (let str of arr) {
frequency[str] = (frequency[str] || 0) + 1;
}
let distinctCount = 0;
for (let str of arr) {
if (frequency[str] === 1) {
distinctCount += 1;
if (distinctCount === k) {
return str;
}
}
}
return "";
}
// Example usage
console.log(kthDistinct(["d","b","c","b","c","a"], 2)); // Output: "a"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.
Time Complexity: O(n).
Space Complexity: O(n), because of the hash map to store frequencies.
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.
function kthDistinct(arr: string[], k: number): string {
const cnt = new Map<string, number>();
for (const s of arr) {
cnt.set(s, (cnt.get(s) || 0) + 1);
}
for (const s of arr) {
if (cnt.get(s) === 1 && --k === 0) {
return s;
}
}
return '';
}func kthDistinct(arr []string, k int) string {
cnt := map[string]int{}
for _, s := range arr {
cnt[s]++
}
for _, s := range arr {
if cnt[s] == 1 {
k--
if k == 0 {
return s
}
}
}
return ""
}use std::collections::HashMap;
impl Solution {
pub fn kth_distinct(arr: Vec<String>, mut k: i32) -> String {
let mut cnt = HashMap::new();
for s in &arr {
*cnt.entry(s).or_insert(0) += 1;
}
for s in &arr {
if *cnt.get(s).unwrap() == 1 {
k -= 1;
if k == 0 {
return s.clone();
}
}
}
"".to_string()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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. |
| Approach 2: Two Pass Filtering with Set | Time Complexity: O(n). |
| Hash Table + Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Count and Order of Appearance | O(n) | O(n) | General case when you need frequency counting and must preserve original order |
| Two Pass Filtering with Set | O(n) | O(n) | Useful when separating duplicate tracking and distinct filtering improves readability |
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.