Sponsored
Sponsored
This approach involves using a dictionary (or hashmap) to count the frequency of each string in the array, and then iterating over the array once more to find the kth distinct string based on the order of appearance.
Time Complexity: O(n), where n is the number of strings in the array, because we make a single pass to record frequencies and another to find the kth distinct string.
Space Complexity: O(n), used for storing the frequency dictionary.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6string kthDistinct(vector<string>& arr, int k) {
7 unordered_map<string, int> frequency;
8 for (const string& str : arr) {
9 frequency[str]++;
10 }
11 int distinct_count = 0;
12 for (const string& str : arr) {
13 if (frequency[str] == 1) {
14 distinct_count++;
15 if (distinct_count == k) {
16 return str;
17 }
18 }
19 }
20 return "";
21}
22
23// Example usage
24int main() {
25 vector<string> arr = {"d","b","c","b","c","a"};
26 int k = 2;
27 cout << kthDistinct(arr, k) << endl; // Output: "a"
28 return 0;
29}Similar to the Python solution, we use an unordered_map to count occurrences of each string. We then iterate over the vector to check which ones are distinct and return the kth found distinct string.
This approach utilizes two passes over the array. In the first pass, we determine distinct elements using a count map. In the second pass, we filter using a set to collect exact distinct strings, maintaining their order.
Time Complexity: O(n).
Space Complexity: O(n), because of the hash map to store frequencies.
1import java.util.*;
2
3
The solution uses a hash map to count the occurrences of strings. In a second iteration, strings that appear only once are considered distinct. Counting these, when the kth distinct element is found, it is returned.