Leetcode 2053: Kth Distinct String in an Array

Input: An array of strings and an integer k.

Example: Input: arr = ["apple", "banana", "cherry", "banana", "apple", "date"], k = 2

Constraints:

• 1 <= k <= arr.length <= 1000

• 1 <= arr[i].length <= 5

• arr[i] consists of lowercase English letters.

Output: The k-th unique string based on order of appearance, or an empty string if fewer than k unique strings exist.

Example: Output: "date" for the given input arr and k.

Constraints:

Goal: Identify and return the k-th unique string.

Steps:

• Iterate through the array and count the occurrences of each string.

• Filter the strings that appear only once, maintaining their original order.

• Return the k-th unique string if it exists; otherwise, return an empty string.

Goal: Conditions that must be met by the inputs.

Steps:

• 1 <= k <= arr.length <= 1000

• 1 <= arr[i].length <= 5

• arr[i] consists of lowercase English letters.

Assumptions:

• All elements in the array are strings.

• Strings are considered case-sensitive.

• The array may contain duplicate strings.

• Input: arr = ["apple", "banana", "cherry", "banana", "apple", "date"], k = 2

• Explanation: Unique strings are ["cherry", "date"]. The 2nd unique string is "date".

Approach: Use a hash map to count occurrences, and then filter strings appearing exactly once.

Observations:

• Strings appearing multiple times can be ignored.

• Order of appearance matters for uniqueness.

• A hash map is ideal for counting occurrences efficiently.

• The result should maintain the original order of the array.

Steps:

• Initialize a hash map to store the frequency of each string.

• Traverse the array to populate the hash map.

• Iterate through the array again, checking for strings with frequency 1.

• Return the k-th unique string if found, otherwise return an empty string.

Empty Inputs:

• Input: arr = [], k = 1; Output: ""

Large Inputs:

• Input: arr contains 1000 strings with no duplicates, k = 1000; Output: Last string in arr.

Special Values:

• Input: arr = ["a", "b", "a"], k = 2; Output: ""

Constraints:

• Input: arr = ["x", "x"], k = 1; Output: ""

string kthDistinct(vector<string>& arr, int k) {
    unordered_map<string, int> mp;
    for (auto &s : arr)
        ++mp[s];
    for (auto &s : arr)
        if (mp[s] == 1 && --k == 0)
            return s;
    return "";
}

1 : Function Declaration

string kthDistinct(vector<string>& arr, int k) {

This line declares the function 'kthDistinct' which takes a vector of strings and an integer k, and returns the k-th distinct string that appears exactly once in the list.

2 : Variable Initialization

    unordered_map<string, int> mp;

This line initializes an unordered map 'mp' to keep track of the frequency of each string in the array.

3 : Loop

    for (auto &s : arr)

This loop iterates over each string 's' in the input array 'arr'.

4 : Map Update

        ++mp[s];

For each string 's', this line increments its frequency in the unordered map 'mp'.

5 : Loop

    for (auto &s : arr)

This loop iterates again through the array 'arr', now checking each string to see if it has appeared exactly once.

6 : Condition Check

        if (mp[s] == 1 && --k == 0)

Checks if the current string appears exactly once in the array (i.e., its count in 'mp' is 1) and whether it is the k-th such string by decrementing 'k'.

7 : Return Statement

            return s;

If the current string 's' is the k-th distinct string, return it as the result.

8 : Return Statement

    return "";

If no such k-th distinct string is found, return an empty string to indicate no result.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: Traversing the array twice contributes to O(n) time complexity.

Best Case: O(n)

Worst Case: O(n)

Description: The hash map requires O(n) space to store frequencies of all strings.

Leetcode 2053: Kth Distinct String in an Array

Explore →