Kth Distinct String in an Array

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

        // First loop to count frequency of each string
        for (string& s : arr) {
            count[s]++;
        }

        // Second loop to locate the k-th unique string
        for (string& s : arr) {
            // Decrement k if the string appears only once
            if (count[s] == 1) {
                k--;
            }
            // Return the string when k is 0
            if (k == 0) {
                return s;
            }
        }

        return "";
    }
};

Below is a solution summary for the problem of finding the k-th distinct string in an array using C++:

The provided C++ code defines a method kthUnique, which finds the k-th unique string in a given array of strings.

• The solution utilizes the unordered_map to count the occurrences of each string in the array.
• The process encompasses two main loops:
  • The first loop iterates through the array arr, using the map count to record the frequency of each string.
  • The second loop again iterates through arr, this time checking for strings that appear exactly once. The variable k is decremented each time a unique string is found.
  • If k reaches zero, the current string, which is the k-th unique string, is returned.

If no such k-th unique string exists (i.e., k is not zero after completing the second loop), the function returns an empty string as the default output.

This method ensures that the first occurrence of each unique string is considered for the count toward k, aligning with its first appearance in the list order from the input array.

class Solution {

    public String findKthDistinct(String[] array, int k) {
        Map<String, Integer> countMap = new HashMap<>();

        // First loop to count occurrences
        for (String element : array) {
            countMap.put(element, countMap.getOrDefault(element, 0) + 1);
        }

        // Second loop to identify the k-th unique element
        for (String element : array) {
            // Identify unique elements
            if (countMap.get(element) == 1) {
                k--;
            }
            // Outcome when k is zero
            if (k == 0) {
                return element;
            }
        }

        return "";
    }
}

The provided Java solution finds the k-th distinct string in an array. It uses a HashMap to count the occurrences of each string in the array. Here's how the solution workflow is structured:

• Count Frequency of Each Element:

  • Iterate through all elements in the input array.
  • Update the frequency count of each string using the HashMap (countMap). If the string is not in the map, initialize its count to 0, then increment by 1.

• Identify and Return the K-th Distinct String:

  • Iterate through the array again.
  • For each element, check if its count in the HashMap is equal to 1, indicating it is unique.
  • Decrement k each time a unique string is encountered.
  • When the decremented value of k reaches 0, the current element is the k-th distinct string. Return this string.

• Handle Non-existence Case:

  • If the function exhausts all the elements in the array and can't find the k-th distinct string, return an empty string.

This approach efficiently tracks and retrieves the k-th distinct string by leveraging the counting map creation and subsequent scanning, supporting cases where some strings may not be distinct. Also, it ensures that the impact of multiple loops is mitigated by not rechecking already identified distinct strings. Hence, it provides a way to find the needed value without excessive computational overhead.

class Solution:
    def findKthDistinct(self, words: List[str], index: int) -> str:
        count_dict = {}

        # Fill dictionary with counts
        for word in words:
            count_dict[word] = count_dict.get(word, 0) + 1

        # Traverse to find the k-th unique element
        for word in words:
            if count_dict[word] == 1:  # Distinct element
                index -= 1
            if index == 0:  # Desired position reached
                return word

        return ""  # Return empty string if no k-th distinct element found

The Python solution provided addresses the problem of finding the kth distinct string in an array. Here's a breakdown of how the solution works:

• It begins by creating a dictionary to store the frequency of each word in the array.

• The solution iterates over the list of words, incrementing the word's count in the dictionary each time it appears in the list.

• It then processes the list again to check for distinct words (words that appear exactly once in the array).

• While traversing the words the second time, the script decrements the given index each time a distinct word is encountered. When the index reaches zero, it implies that we've reached the kth distinct element, and the function returns the word at that position.

• If the index does not reach zero (meaning there aren't enough distinct words), the function returns an empty string.

This approach efficiently provides the kth distinct word by using a dictionary for counting and a simple iteration to retrieve the desired element based on its distinct count. The complexity mainly depends on the size of the input list for both space and time since each element is processed and stored in the dictionary.