Description (leetcode)

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 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 1^st, so it is the 1^st distinct string.

“a” appears 2^nd, so it is the 2^nd 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 1^st 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.

submission

// one line just for fun
impl Solution {
    pub fn kth_distinct(arr: Vec<String>, k: i32) -> String {
        arr.into_iter()
            .enumerate()
            // collect every indices of a string
            .fold(
                std::collections::HashMap::<String, Vec<usize>>::new(),
                |mut indices, (idx, s)| {
                    indices.entry(s).or_default().push(idx);
                    indices
                }
            )
            .into_iter()
            // filter with pattern matching
            .filter_map(|(s, indices)| {
                match &indices[..] {
                    &[idx] => Some((idx, s)),
                    _ => None,
                }
            })
            // sort with binary heap
            .collect::<std::collections::BinaryHeap<(usize, String)>>()
            .into_sorted_vec()
            .into_iter()
            // take the k - 1 one
            .nth((k - 1) as usize)
            .map(|(_, s)| s)
            .unwrap_or_default()
    }
}