[LeetCode] 2053. Kth Distinct String in an Array

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.

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

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

思路

需要遍历两遍 input 数组。第一遍遍历，用 hashmap 记录每个不同字符的出现次数。第二次遍历，挑出所有只出现过一次的字符串，放在一个 list 中。遍历结束后，如果 list 的长度不足 k，则返回空字符串；反之则返回第 k 个字符串。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String kthDistinct(String[] arr, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String str : arr) {
            map.put(str, map.getOrDefault(str, 0) + 1);
        }

        List<String> res = new ArrayList<>();
        for (String str : arr) {
            if (map.get(str) == 1) {
                res.add(str);
            }
        }
        if (res.size() < k) {
            return "";
        }
        return res.get(k - 1);
    }
}