What is the time complexity of solving the Kth Distinct String in an Array?

The time complexity is O(n), where `n` is the length of the array. The array is scanned once, and each string lookup or insertion in the hash map takes constant time.

What should I do if there are fewer than `k` distinct strings in the array?

If there are fewer than `k` distinct strings, the solution should return an empty string, as there is no kth distinct string.

What’s the main pattern used to solve the Kth Distinct String in an Array problem?

The main pattern is array scanning combined with hash map lookups. This allows you to efficiently track distinct strings and return the kth one when found.

How do I handle duplicate strings in the Kth Distinct String in an Array?

Duplicates are ignored when identifying distinct strings. Only strings that appear exactly once are considered distinct.

What are the space complexity and how do they affect the solution?

The space complexity is O(n), where `n` is the number of strings in the array. This is due to the need for storing the count of each string in a hash map.

#2053

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

数组中第 K 个独一无二的字符串

独一无二的字符串指的是在一个数组中只出现过一次的字符串。给你一个字符串数组 arr 和一个整数 k ，请你返回 arr 中第 k 个独一无二的字符串。如果少于 k 个独一无二的字符串，那么返回空字符串 "" 。注意，按照字符串在原数组中的顺序找到第 k 个独一无二字符串。示例…

数组哈希表字符串计数

题目描述

独一无二的字符串 指的是在一个数组中只出现过一次的字符串。

给你一个字符串数组 arr 和一个整数 k ，请你返回 arr 中第 k 个 独一无二的字符串 。如果少于 k 个独一无二的字符串，那么返回 空字符串 "" 。

注意，按照字符串在原数组中的顺序找到第 k 个独一无二字符串。

示例 1:

输入：arr = ["d","b","c","b","c","a"], k = 2
输出："a"
解释：
arr 中独一无二字符串包括 "d" 和 "a" 。
"d" 首先出现，所以它是第 1 个独一无二字符串。
"a" 第二个出现，所以它是 2 个独一无二字符串。
由于 k == 2 ，返回 "a" 。

示例 2:

输入：arr = ["aaa","aa","a"], k = 1
输出："aaa"
解释：
arr 中所有字符串都是独一无二的，所以返回第 1 个字符串 "aaa" 。

示例 3：

输入：arr = ["a","b","a"], k = 3
输出：""
解释：
唯一一个独一无二字符串是 "b" 。由于少于 3 个独一无二字符串，我们返回空字符串 "" 。

提示：

1 <= k <= arr.length <= 1000
1 <= arr[i].length <= 5
arr[i] 只包含小写英文字母。

lightbulb

解题思路

方法一：哈希表 + 计数

我们可以用一个哈希表 $\textit{cnt}$ 记录每个字符串出现的次数，然后再遍历一次数组，对于每个字符串，如果它出现的次数为 $1$ ，那么就将 $k$ 减一，直到 $k$ 减为 $0$ ，返回当前字符串即可。

时间复杂度 $O(L)$ ，空间复杂度 $O(L)$ ，其中 $L$ 为数组 $\textit{arr}$ 所有字符串的长度之和。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def kthDistinct(self, 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 ""

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Check for familiarity with hash maps and array scanning.
question_mark
Verify the candidate's understanding of distinct elements and efficient lookups.
question_mark
Evaluate their approach to handling edge cases, especially with fewer distinct strings.

warning

常见陷阱

外企场景

error
Misunderstanding what counts as a distinct string; strings must appear only once in the array.
error
Failing to handle the case where fewer than `k` distinct strings exist, leading to incorrect results.
error
Not efficiently using a hash map or failing to terminate the scan early when `k` distinct strings are found.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the first distinct string instead of the kth one.
arrow_right_alt
Modify the function to return the kth most frequent distinct string.
arrow_right_alt
Handle larger arrays with optimized space and time complexities, exploring advanced hashing techniques.

help

常见问题

外企场景

继续练习

#2023 连接后等于目标字符串的字符串对 #2085 统计出现过一次的公共字符串 #2131 连接两字母单词得到的最长回文串