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.

Approach 01:

#include <vector>
#include <string>
#include <unordered_map>
#include <iostream>
using namespace std;

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

        // Count the frequency of each string in the array
        for (const string& str : arr) {
            frequencyMap[str]++;
        }

        // Iterate through the array to find the k-th distinct string
        for (const string& str : arr) {
            if (frequencyMap[str] == 1) {
                k--;
                if (k == 0) {
                    return str;  // Return the k-th distinct string
                }
            }
        }

        return "";  // If there are fewer than k distinct strings, return an empty string
    }
};

from typing import List
from collections import Counter

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        frequencyMap = Counter(arr)

        # Iterate through the array to find the k-th distinct string
        for str in arr:
            if frequencyMap[str] == 1:
                k -= 1
                if k == 0:
                    return str  # Return the k-th distinct string

        return ""  # If there are fewer than k distinct strings, return an empty string

Time Complexity

• Counting Frequencies:

  Iterating through the array to count the frequencies of each string takes \( O(n) \) time, where \( n \) is the number of elements in the array.

• Finding the k-th Distinct String:

  Iterating through the array again to find the k-th distinct string takes \( O(n) \) time.

• Overall Time Complexity:

  Combining these steps, the overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The space complexity for the frequency map is \( O(n) \) since, in the worst case, we store one entry for each string in the array.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \).