2053. Kth Distinct String in an Array - Explanation

Description

A distinct string is a string that is present only once in an array.

You are given an array of strings arr, and an integer k, return the k-th 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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps - Counting occurrences of elements with O(1) average lookup and insertion
Hash Sets - Tracking unique elements and checking membership efficiently
Array Traversal - Iterating through arrays while maintaining order

1. Brute Force

Intuition

A string is distinct if it appears exactly once in the array. The simplest approach is to check each string against all other strings. For each position, we scan the entire array to see if that string appears anywhere else. If not, it's distinct, and we decrement our counter until we find the k-th one.

Algorithm

Iterate through each string at index i.
For each string, check all other positions j to see if there's a duplicate.
If no duplicate is found, the string is distinct; decrement k.
When k reaches 0, return the current string.
If we exhaust all strings without finding k distinct ones, return an empty string.

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        for i in range(len(arr)):
            flag = True
            for j in range(len(arr)):
                if i == j:
                    continue

                if arr[i] == arr[j]:
                    flag = False
                    break

            if flag:
                k -= 1
                if k == 0:
                    return arr[i]
        return ""

public class Solution {
    public String kthDistinct(String[] arr, int k) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length; j++) {
                if (i == j) continue;

                if (arr[i].equals(arr[j])) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                k--;
                if (k == 0) {
                    return arr[i];
                }
            }
        }
        return "";
    }
}

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        for (int i = 0; i < arr.size(); i++) {
            bool flag = true;
            for (int j = 0; j < arr.size(); j++) {
                if (i == j) continue;

                if (arr[i] == arr[j]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                k--;
                if (k == 0) {
                    return arr[i];
                }
            }
        }
        return "";
    }
};

class Solution {
    /**
     * @param {string[]} arr
     * @param {number} k
     * @return {string}
     */
    kthDistinct(arr, k) {
        for (let i = 0; i < arr.length; i++) {
            let flag = true;
            for (let j = 0; j < arr.length; j++) {
                if (i === j) continue;

                if (arr[i] === arr[j]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                k--;
                if (k === 0) {
                    return arr[i];
                }
            }
        }
        return '';
    }
}

public class Solution {
    public string KthDistinct(string[] arr, int k) {
        for (int i = 0; i < arr.Length; i++) {
            bool flag = true;
            for (int j = 0; j < arr.Length; j++) {
                if (i == j) continue;

                if (arr[i] == arr[j]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                k--;
                if (k == 0) {
                    return arr[i];
                }
            }
        }
        return "";
    }
}

func kthDistinct(arr []string, k int) string {
    for i := 0; i < len(arr); i++ {
        flag := true
        for j := 0; j < len(arr); j++ {
            if i == j {
                continue
            }

            if arr[i] == arr[j] {
                flag = false
                break
            }
        }

        if flag {
            k--
            if k == 0 {
                return arr[i]
            }
        }
    }
    return ""
}

class Solution {
    fun kthDistinct(arr: Array<String>, k: Int): String {
        var cnt = k
        for (i in arr.indices) {
            var flag = true
            for (j in arr.indices) {
                if (i == j) continue

                if (arr[i] == arr[j]) {
                    flag = false
                    break
                }
            }

            if (flag) {
                cnt--
                if (cnt == 0) {
                    return arr[i]
                }
            }
        }
        return ""
    }
}

class Solution {
    func kthDistinct(_ arr: [String], _ k: Int) -> String {
        var cnt = k
        for i in 0..<arr.count {
            var flag = true
            for j in 0..<arr.count {
                if i == j { continue }

                if arr[i] == arr[j] {
                    flag = false
                    break
                }
            }

            if flag {
                cnt -= 1
                if cnt == 0 {
                    return arr[i]
                }
            }
        }
        return ""
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Hash Map

Intuition

Instead of repeatedly scanning the array, we can count occurrences upfront using a hash map. In the first pass, we count how many times each string appears. In the second pass, we iterate in order and check if each string has a count of exactly 1. This reduces time complexity from O(n^2) to O(n).

Algorithm

Create a hash map to count occurrences of each string.
Iterate through the array, incrementing the count for each string.
Iterate through the array again in order.
For each string with count equal to 1, decrement k.
Return the string when k becomes 0, or return an empty string if not found.

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        count = {}

        for s in arr:
            if s not in count:
                count[s] = 0
            count[s] += 1

        for s in arr:
            if count[s] == 1:
                k -= 1
                if k == 0:
                    return s

        return ""

public class Solution {
    public String kthDistinct(String[] arr, int k) {
        Map<String, Integer> count = new HashMap<>();

        for (String s : arr) {
            count.put(s, count.getOrDefault(s, 0) + 1);
        }

        for (String s : arr) {
            if (count.get(s) == 1) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }

        return "";
    }
}

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        unordered_map<string, int> count;

        for (const string& s : arr) {
            count[s]++;
        }

        for (const string& s : arr) {
            if (count[s] == 1) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }

        return "";
    }
};

class Solution {
    /**
     * @param {string[]} arr
     * @param {number} k
     * @return {string}
     */
    kthDistinct(arr, k) {
        const count = {};

        for (let s of arr) {
            if (!(s in count)) {
                count[s] = 0;
            }
            count[s]++;
        }

        for (let s of arr) {
            if (count[s] === 1) {
                k--;
                if (k === 0) {
                    return s;
                }
            }
        }

        return '';
    }
}

public class Solution {
    public string KthDistinct(string[] arr, int k) {
        var count = new Dictionary<string, int>();

        foreach (string s in arr) {
            if (!count.ContainsKey(s)) {
                count[s] = 0;
            }
            count[s]++;
        }

        foreach (string s in arr) {
            if (count[s] == 1) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }

        return "";
    }
}

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

    for _, s := range arr {
        count[s]++
    }

    for _, s := range arr {
        if count[s] == 1 {
            k--
            if k == 0 {
                return s
            }
        }
    }

    return ""
}

class Solution {
    fun kthDistinct(arr: Array<String>, k: Int): String {
        val count = mutableMapOf<String, Int>()

        for (s in arr) {
            count[s] = count.getOrDefault(s, 0) + 1
        }

        var cnt = k
        for (s in arr) {
            if (count[s] == 1) {
                cnt--
                if (cnt == 0) {
                    return s
                }
            }
        }

        return ""
    }
}

class Solution {
    func kthDistinct(_ arr: [String], _ k: Int) -> String {
        var count = [String: Int]()

        for s in arr {
            count[s, default: 0] += 1
        }

        var cnt = k
        for s in arr {
            if count[s] == 1 {
                cnt -= 1
                if cnt == 0 {
                    return s
                }
            }
        }

        return ""
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Hash Set

Intuition

We can use two sets instead of a counting map. One set tracks strings that are currently distinct (seen exactly once), and another tracks strings we've already identified as duplicates. When we encounter a string, if it's in the distinct set, we move it to the seen set (it's no longer distinct). If it's not in either set, we add it to distinct. This achieves the same result with a slightly different data structure.

Algorithm

Create two sets: distinct for unique strings and seen for duplicates.
For each string in the array:
- If it's in distinct, move it to seen (it's now a duplicate).
- If it's not in seen, add it to distinct.
Iterate through the array again in order.
For strings in the distinct set, decrement k.
Return the string when k reaches 0.

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        distinct, seen = set(), set()

        for s in arr:
            if s in distinct:
                distinct.remove(s)
                seen.add(s)
            elif s not in seen:
                distinct.add(s)

        for s in arr:
            if s in distinct:
                k -= 1
                if k == 0:
                    return s

        return ""

public class Solution {
    public String kthDistinct(String[] arr, int k) {
        Set<String> distinct = new HashSet<>();
        Set<String> seen = new HashSet<>();

        for (String s : arr) {
            if (distinct.contains(s)) {
                distinct.remove(s);
                seen.add(s);
            } else if (!seen.contains(s)) {
                distinct.add(s);
            }
        }

        for (String s : arr) {
            if (distinct.contains(s)) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }

        return "";
    }
}

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        unordered_set<string> distinct, seen;

        for (const string& s : arr) {
            if (distinct.count(s)) {
                distinct.erase(s);
                seen.insert(s);
            } else if (!seen.count(s)) {
                distinct.insert(s);
            }
        }

        for (const string& s : arr) {
            if (distinct.count(s)) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }

        return "";
    }
};

class Solution {
    /**
     * @param {string[]} arr
     * @param {number} k
     * @return {string}
     */
    kthDistinct(arr, k) {
        const distinct = new Set();
        const seen = new Set();

        for (let s of arr) {
            if (distinct.has(s)) {
                distinct.delete(s);
                seen.add(s);
            } else if (!seen.has(s)) {
                distinct.add(s);
            }
        }

        for (let s of arr) {
            if (distinct.has(s)) {
                k--;
                if (k === 0) {
                    return s;
                }
            }
        }

        return '';
    }
}

public class Solution {
    public string KthDistinct(string[] arr, int k) {
        var distinct = new HashSet<string>();
        var seen = new HashSet<string>();

        foreach (string s in arr) {
            if (distinct.Contains(s)) {
                distinct.Remove(s);
                seen.Add(s);
            } else if (!seen.Contains(s)) {
                distinct.Add(s);
            }
        }

        foreach (string s in arr) {
            if (distinct.Contains(s)) {
                k--;
                if (k == 0) {
                    return s;
                }
            }
        }

        return "";
    }
}

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

    for _, s := range arr {
        if distinct[s] {
            delete(distinct, s)
            seen[s] = true
        } else if !seen[s] {
            distinct[s] = true
        }
    }

    for _, s := range arr {
        if distinct[s] {
            k--
            if k == 0 {
                return s
            }
        }
    }

    return ""
}

class Solution {
    fun kthDistinct(arr: Array<String>, k: Int): String {
        val distinct = mutableSetOf<String>()
        val seen = mutableSetOf<String>()

        for (s in arr) {
            if (s in distinct) {
                distinct.remove(s)
                seen.add(s)
            } else if (s !in seen) {
                distinct.add(s)
            }
        }

        var cnt = k
        for (s in arr) {
            if (s in distinct) {
                cnt--
                if (cnt == 0) {
                    return s
                }
            }
        }

        return ""
    }
}

class Solution {
    func kthDistinct(_ arr: [String], _ k: Int) -> String {
        var distinct = Set<String>()
        var seen = Set<String>()

        for s in arr {
            if distinct.contains(s) {
                distinct.remove(s)
                seen.insert(s)
            } else if !seen.contains(s) {
                distinct.insert(s)
            }
        }

        var cnt = k
        for s in arr {
            if distinct.contains(s) {
                cnt -= 1
                if cnt == 0 {
                    return s
                }
            }
        }

        return ""
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Counting Distinct Strings Out of Order

The k-th distinct string must be found in the original array order, not in any arbitrary order. A common mistake is collecting all distinct strings into a set and then trying to find the k-th one, but sets do not preserve insertion order in all languages. Always iterate through the original array in order when finding the k-th distinct string.

Returning Before Finding the K-th Distinct String

If there are fewer than k distinct strings in the array, the function should return an empty string. Forgetting to handle this edge case or returning the last found distinct string instead of an empty string leads to incorrect results. Always check if k reaches zero before returning, and return empty string if the loop completes without finding enough distinct strings.