2053. Kth Distinct String in an Array
Problem Description
In this problem, we are given an array of strings, arr
, where we need to identify strings that appear exactly once in the array, which we refer to as "distinct strings." Our goal is to find the k
th distinct string in the array, considering the order in which the strings appear. If the number of distinct strings in the array is less than k
, we should return an empty string ""
. Essentially, the problem is asking us to process the array and extract a specific element based on its distinctness and order of occurrence.
Intuition
The solution for this problem involves two steps:
- Counting the occurrence of each string in the array.
- Iterating through the array to find the
k
th string that occurs exactly once.
To efficiently count occurrences, we use a data structure known as a counter (which can be provided by Python's collections.Counter
class). This counter keeps track of how many times each string appears in the array.
Once we have the occurrences counted, the next step is to iterate through the array while keeping track of the number of distinct strings encountered so far. A string is considered distinct if its counted occurrence is equal to one. We sequentially check each string's occurrence count, decreasing k
each time we find a distinct string.
When k
becomes 0, that means we've encountered the k
th distinct string and can return it immediately. If the end of the array is reached and k
has not reached 0, we return an empty string because there aren't enough distinct strings in the array.
Solution Approach
The solution is implemented in Python and follows these steps:
- Counting Occurrences: We first create a
counter
object from Python'scollections.Counter
class to count the occurrences of every string in the arrayarr
. TheCounter
class generates a dictionary-like object where each key is a unique string fromarr
, and the corresponding value is the count of that string's occurrences.
counter = Counter(arr)
- Finding the kth Distinct String: We then iterate over the original array
arr
since we need to respect the order of strings. For each stringv
inarr
, we look at its count in thecounter
.
for v in arr: if counter[v] == 1:
If the count is 1, it signifies that v
is a distinct string. We decrement k
for each distinct string found.
- Checking the kth Position: If during iteration
k
becomes 0, this implies that we have found thek
th distinct string, and we immediately return this stringv
.
k -= 1 if k == 0: return v
- Returning an Empty String: If the loop finishes and no string has made
k
reach 0, this means that there are fewer thank
distinct strings in the array. Hence, the function returns an empty string''
.
return ''
This implementation is efficient because it traverses the list only once to count the elements and a second time to find the kth distinct element. The counter object provides an O(1) access time to find an element's count, ensuring that the solution is linear with respect to the size of the input array, which is optimal for this problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Imagine we are given the following array of strings arr
and we want to find the 2nd
distinct string:
arr = ["apple", "banana", "apple", "orange", "banana", "kiwi"]
Counting Occurrences: First, we use the counter to count the occurrences of each string:
counter = Counter(arr) # {'apple': 2, 'banana': 2, 'orange': 1, 'kiwi': 1}
Finding the kth Distinct String: The counter tells us that "apple" and "banana" are not distinct (both appear twice). However, "orange" and "kiwi" are distinct (each appears once). As we wish to find the 2nd distinct string, we start iterating through arr
:
- We encounter "apple" first. Its occurrence count is 2, so it's not distinct.
- We move to "banana" with the same result as "apple".
- Next is "apple" again, still not distinct.
- Then we encounter "orange", which is distinct since its count is 1.
- We set
k
to 2 initially. Now we decrementk
to 1 as we have found our 1st distinct string.
- We set
- We move on to "banana" once more, which is also not distinct.
- Lastly, we find "kiwi", which has a count of 1 and is therefore distinct.
- We decrement
k
again and nowk
is 0, which means "kiwi" is our 2nd distinct string.
- We decrement
Checking the kth Position: Since we found the 2nd distinct string and k
is now 0
, we return "kiwi".
If instead k
was set to 3
initially, after going through the array, we would still be left with k
equals 1
, meaning there wasn't a 3rd distinct string. In that case, we'd return an empty string ""
.
Returning an Empty String: Since in this example there are only 2 distinct strings and we found the 2nd, there's no need to return an empty string. If we were looking for the 3rd distinct string which does not exist in our arr
, our result would be ""
.
By following this method, we call the Counter class once to build our occurrence dictionary and then iterate through the array only once more, making this a very efficient way to solve the problem.
Solution Implementation
1from collections import Counter # Import the Counter class from collections module
2
3class Solution:
4 def kthDistinct(self, arr: List[str], k: int) -> str:
5 # Create a counter for all items in arr
6 # Counter will store words as keys and their occurrences as values
7 occurrence_counter = Counter(arr)
8
9 # Iterate over each word in arr
10 for word in arr:
11 # Check if the current word occurs exactly once
12 if occurrence_counter[word] == 1:
13 # Decrement k as we've found one distinct word
14 k -= 1
15 # If k reaches 0, we've found the kth distinct word
16 if k == 0:
17 return word
18
19 # If the kth distinct word is not found, return an empty string
20 return ''
21
1class Solution {
2
3 // Method to find the k-th distinct string in the array
4 public String kthDistinct(String[] arr, int k) {
5 // Create a HashMap to store the frequency of each string
6 Map<String, Integer> frequencyMap = new HashMap<>();
7
8 // Count the occurrences of each string in the array
9 for (String element : arr) {
10 frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1);
11 }
12
13 // Iterate over the array to find the k-th distinct string
14 for (String element : arr) {
15 // If the frequency of the string is 1, it is distinct
16 if (frequencyMap.get(element) == 1) {
17 k--; // Decrement k for each distinct string found
18
19 // If k reaches zero, we found the k-th distinct string
20 if (k == 0) {
21 return element;
22 }
23 }
24 }
25
26 // If k distinct strings are not found, return an empty string
27 return "";
28 }
29}
30
1#include <string>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6class Solution {
7public:
8 // Function to find the k-th distinct string in the array.
9 string kthDistinct(vector<string>& arr, int k) {
10 // Create a hash map to store the frequency of each string.
11 unordered_map<string, int> frequencyMap;
12
13 // Count the frequency of each string in the array.
14 for (const string& value : arr) {
15 ++frequencyMap[value];
16 }
17
18 // Iterate through the array to find the k-th distinct string.
19 for (const string& value : arr) {
20 // Check if the current string is distinct (frequency is 1).
21 if (frequencyMap[value] == 1) {
22 // Decrement k and check if we have found the k-th distinct string.
23 --k;
24 if (k == 0) {
25 // If k reaches 0, the current string is the k-th distinct string.
26 return value;
27 }
28 }
29 }
30
31 // If the k-th distinct string is not found, return an empty string.
32 return "";
33 }
34};
35
1// Importing required types for TypeScript
2import { string } from "prop-types";
3
4// Function to find the k-th distinct string in the array.
5function kthDistinct(arr: string[], k: number): string {
6 // Create a map to store the frequency of each string.
7 const frequencyMap: Record<string, number> = {};
8
9 // Count the frequency of each string in the array.
10 for (const value of arr) {
11 // Increase the frequency count for the string in the map.
12 frequencyMap[value] = (frequencyMap[value] || 0) + 1;
13 }
14
15 // Iterate through the array to find the k-th distinct string.
16 for (const value of arr) {
17 // Check if the current string is distinct (frequency is 1).
18 if (frequencyMap[value] === 1) {
19 // Decrement k and check if we have found the k-th distinct string.
20 k--;
21 if (k === 0) {
22 // If k reaches 0, the current string is the k-th distinct string.
23 return value;
24 }
25 }
26 }
27
28 // If the k-th distinct string is not found, return an empty string.
29 return "";
30}
31
32// Example usage:
33// const strings = ["a", "b", "a"];
34// const result = kthDistinct(strings, 2); // Should return "b" if called
35
Time and Space Complexity
The given Python code snippet defines a method kthDistinct
which finds the k-th distinct string in the provided arr
list. The computational complexity analysis is as follows:
Time Complexity
The time complexity of the code can be broken down into the following steps:
-
Counter Creation:
counter = Counter(arr)
creates a counter object which counts the occurrences of each distinct value inarr
. Constructing this counter takesO(n)
time, wheren
is the number of elements inarr
. -
Iteration and Checks: The code then iterates over each value in
arr
, this iteration takesO(n)
time. Within the loop, it performs a constant-time checkif counter[v] == 1
for each valuev
, which does not affect the overall O(n) time complexity.
Overall, since both steps are sequential, the total time complexity is O(n) + O(n)
which simplifies to O(n)
.
Space Complexity
The space complexity of the code also involves two major components:
-
Counter Storage: Storing counts of each unique value in
arr
requiresO(m)
space, wherem
is the number of distinct elements inarr
. -
Loop Variables: The loop variables (
v
andk
) and the space for storing function arguments use constantO(1)
space.
Thus, the combined space complexity is O(m)
.
The markdown results display the formulas within "`" to properly markup the complexity notations.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!