Kth Distinct String in an Array

Easy
1193.

Kth Distinct String in an Array

Kth Distinct String in an Array is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

A string of the array arr is distinct when it appears in arr exactly once.

Return the k-th distinct string, counting in the order the strings appear in arr (the first distinct string is the 1st). If arr has fewer than k distinct strings, return the empty string "".

Example 1

Input
arr = ["kai","ro","kai","duel","bug"], k = 2
Output
duel
Explanation
The distinct strings, in order, are `ro`, `duel`, `bug`.

Example 2

Input
arr = ["x","y","x","y"], k = 1
Output
""
Explanation
No string appears exactly once, so the answer is the empty string.

Example 3

Input
arr = ["a","b","c"], k = 3
Output
c

Constraints

  • 1 <= k <= arr.length <= 1000
  • 1 <= arr[i].length <= 5
  • arr[i] consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} arr
 * @param {number} k
 * @return {string}
 */
var kthDistinct = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Kth Distinct String in an Array — Problem & Solution

Kth Distinct String in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Kth Distinct String in an Array is an easy coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, Hash Table, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string of the array arr is distinct when it appears in arr exactly once.

Return the k-th distinct string, counting in the order the strings appear in arr (the first distinct string is the 1st). If arr has fewer than k distinct strings, return the empty string "".

Example 1

Input: arr = ["kai","ro","kai","duel","bug"], k = 2
Output: duel
Explanation: The distinct strings, in order, are `ro`, `duel`, `bug`.

Example 2

Input: arr = ["x","y","x","y"], k = 1
Output: ""
Explanation: No string appears exactly once, so the answer is the empty string.

Example 3

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

Constraints

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

Hints for Kth Distinct String in an Array

  1. Hint 1

    First find out how many times every string occurs.

  2. Hint 2

    A hash map from string to count does it in one pass.

  3. Hint 3

    Then walk arr in order, counting down k on each string whose count is 1; the one that brings k to 0 is the answer.

How to solve Kth Distinct String in an Array

Two passes: count every string, then scan the array in its original order and pick the k-th string whose count is exactly one.

Approach

  1. Build a map count[s] over arr.
  2. Scan arr from left to right; whenever count[s] == 1, decrement k.
  3. When k reaches 0, return the current string.
  4. If the scan ends first, return "".

Why it works

The first pass gives the exact multiplicity of each string, so the second pass recognises distinct strings correctly; it visits them in array order, so the string at which the counter reaches zero is the k-th distinct one. A distinct string appears once, so it cannot be counted twice.

Complexity

  • Time — O(n · L) with L ≤ 5
  • Space — O(n · L)

Pitfalls

  • "Distinct" means appearing exactly once, not "first occurrence of each value".
  • Keep the original order — iterating the hash map would scramble it.
  • Return the empty string, not null, when there are fewer than k distinct strings.

Reference solution

Python

from typing import List
from collections import Counter

def kthDistinct(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 ""

Java

public static String kthDistinct(String[] arr, int k) {
    Map<String, Integer> cnt = new HashMap<>();
    for (String s : arr) cnt.merge(s, 1, Integer::sum);
    for (String s : arr) {
        if (cnt.get(s) == 1) {
            k--;
            if (k == 0) return s;
        }
    }
    return "";
}

C++

string kthDistinct(vector<string>& arr, int k) {
    unordered_map<string, int> cnt;
    for (const string& s : arr) cnt[s]++;
    for (const string& s : arr) {
        if (cnt[s] == 1) {
            k--;
            if (k == 0) return s;
        }
    }
    return "";
}

JavaScript

var kthDistinct = function(arr, k) {
    var cnt = new Map();
    for (var i = 0; i < arr.length; i++) cnt.set(arr[i], (cnt.get(arr[i]) || 0) + 1);
    for (var j = 0; j < arr.length; j++) {
        if (cnt.get(arr[j]) === 1) {
            k--;
            if (k === 0) return arr[j];
        }
    }
    return "";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings