2053-KthDistinctStringInAnArray.go

package main

// 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.

import "fmt"

func kthDistinct(arr []string, k int) string {
    mp := make(map[string]int)
    for _, v := range arr { // 统计字符出现次数
        mp[v]++
    }
    count := 0
    for _, v := range arr {
        if mp[v] == 1 { // distinct strings
            count++
        }
        if count == k { // 出了第 k 个
            return v
        }
    } 
    return ""
}

func kthDistinct1(arr []string, k int) string {
    mp := make(map[string]int)
    for _, v := range arr {
        mp[v]++
    }
    for _, v := range arr {
        if mp[v] == 1 {
            k --
        }
        if k == 0 {
            return v
        }
    }
    return ""
}

func main() {
    // 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. 
    fmt.Println(kthDistinct([]string{ "d","b","c","b","c","a" },2)) // a
    // 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.
    fmt.Println(kthDistinct([]string{ "aaa","aa","a" }, 1)) // aaa
    // 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 "".
    fmt.Println(kthDistinct([]string{ "a","b","a" }, 3)) // " "

    fmt.Println(kthDistinct1([]string{ "d","b","c","b","c","a" },2)) // a
    fmt.Println(kthDistinct1([]string{ "aaa","aa","a" }, 1)) // aaa
    fmt.Println(kthDistinct1([]string{ "a","b","a" }, 3)) // " "
}