# Kth Distinct String in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/kth-distinct-string-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/kth-distinct-string-in-an-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
---
## Problem
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.

# Approaches
## Brute Force with Nested Loops
This approach uses a straightforward, brute-force method. It iterates through each string in the array and, for each one, performs another full scan of the array to count its total occurrences. If a string's count is exactly one, it's considered distinct. A separate counter tracks how many distinct strings have been found in their original order to identify the k-th one.
**Time:** O(N^2 * L), where N is the number of strings in the array and L is the maximum length of a string. For each of the N strings, we iterate through the entire array again (N times), and each string comparison takes O(L) time. Since L is small (<=5), this is effectively O(N^2). · **Space:** O(1). The algorithm uses only a few variables for counting, so the space used is constant and does not depend on the size of the input array.
**Pros:** Simple to understand and implement.; Requires no extra space, making it very memory-efficient.
**Cons:** Highly inefficient for larger arrays due to its O(N^2) time complexity.
### Explanation
The algorithm maintains a `distinctCount` to keep track of the number of distinct strings encountered so far. It employs a nested loop structure. The outer loop iterates through the array from index `i = 0` to `n-1`. For each element `arr[i]`, the inner loop iterates through the entire array (from `j = 0` to `n-1`) to count how many times `arr[i]` appears. After the inner loop completes, if the count for `arr[i]` is 1, it signifies that the string is distinct. We then increment `distinctCount`. If `distinctCount` now equals `k`, we have found our target string, and `arr[i]` is returned. If the outer loop finishes without finding the k-th distinct string, it implies there are fewer than `k` distinct strings, so an empty string `""` is returned.

```java
class Solution {
    public String kthDistinct(String[] arr, int k) {
        int distinctCount = 0;
        for (int i = 0; i < arr.length; i++) {
            int count = 0;
            // Inner loop to count occurrences of arr[i]
            for (int j = 0; j < arr.length; j++) {
                if (arr[i].equals(arr[j])) {
                    count++;
                }
            }
            
            // Check if the string is distinct
            if (count == 1) {
                distinctCount++;
                // Check if it's the k-th distinct string
                if (distinctCount == k) {
                    return arr[i];
                }
            }
        }
        
        // K-th distinct string not found
        return "";
    }
}
```
### Algorithm
- Initialize a counter `distinctCount` to 0.
- Iterate through the input array `arr` with an index `i` from `0` to `n-1`.
- For each string `arr[i]`, start an inner loop to count its occurrences.
  - Initialize a `frequency` counter to 0.
  - Iterate through the array `arr` again with an index `j` from `0` to `n-1`.
  - If `arr[i]` is equal to `arr[j]`, increment `frequency`.
- After the inner loop, check if `frequency` is exactly 1. This indicates `arr[i]` is a distinct string.
- If it is distinct, increment `distinctCount`.
- If `distinctCount` equals `k`, then `arr[i]` is the k-th distinct string. Return `arr[i]`.
- If the outer loop completes and no string has been returned, it means there are fewer than `k` distinct strings. Return an empty string `""`.

## Two-Pass Approach with Hash Map
This optimized approach uses a hash map to efficiently count the frequency of each string in a single pass. A second pass is then made through the original array to find the k-th string that has a frequency of one. This two-pass method preserves the original order of strings while being much faster than the brute-force approach.
**Time:** O(N * L), where N is the number of strings and L is their average length. The first pass to build the map takes O(N * L) time (N insertions/updates, each taking O(L) for hashing/comparison). The second pass also takes O(N * L) in the worst case. The total time complexity is linear with respect to the total number of characters. · **Space:** O(M * L), where M is the number of unique strings in the array and L is their average length. This space is required to store the unique strings and their counts in the hash map. In the worst case, all strings are unique (`M = N`), leading to O(N * L) space complexity.
**Pros:** Significantly more time-efficient than the brute-force approach, with a linear time complexity.; The logic is clear and follows a common pattern for frequency-based problems.
**Cons:** Requires extra space to store the frequency map, which can be proportional to the number of unique strings in the input.
### Explanation
The solution is broken down into two main steps or "passes".

**First Pass (Frequency Counting):** We iterate through the input array `arr` once. We use a `HashMap<String, Integer>` to store each string as a key and its frequency as the value. For each string we encounter, we increment its count in the map. This gives us a complete frequency profile of all strings in O(N * L) time.

**Second Pass (Finding the k-th Distinct String):** We iterate through the input array `arr` a second time, from beginning to end. This is crucial to respect the original order of appearance. For each string, we look up its frequency in the map we built in the first pass. If the frequency is exactly 1, we've found a distinct string. We use a counter to track how many distinct strings we've seen in this pass. When the counter reaches `k`, we return the current string. If we finish the second pass and haven't found `k` distinct strings, we return an empty string `""`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String kthDistinct(String[] arr, int k) {
        Map<String, Integer> counts = new HashMap<>();
        // First pass: count frequencies
        for (String s : arr) {
            counts.put(s, counts.getOrDefault(s, 0) + 1);
        }

        int distinctCount = 0;
        // Second pass: find the k-th distinct string in original order
        for (String s : arr) {
            if (counts.get(s) == 1) {
                distinctCount++;
                if (distinctCount == k) {
                    return s;
                }
            }
        }

        return "";
    }
}
```
### Algorithm
- Create a `HashMap<String, Integer>` to store the frequency of each string.
- **First Pass:** Iterate through each string `s` in the input array `arr`.
  - For each `s`, update its count in the hash map. Use `map.put(s, map.getOrDefault(s, 0) + 1)` for a concise update.
- Initialize a counter `distinctCount` to 0.
- **Second Pass:** Iterate through the input array `arr` again, in its original order.
  - For each string `s`, retrieve its count from the hash map.
  - If the count is 1, it's a distinct string. Increment `distinctCount`.
  - If `distinctCount` equals `k`, return the current string `s`.
- If the second pass completes without returning a string, it means there are fewer than `k` distinct strings. Return an empty string `""`.

# Solutions
### Java

```java
class Solution {
public
  String kthDistinct(String[] arr, int k) {
    Map<String, Integer> counter = new HashMap<>();
    for (String v : arr) {
      counter.put(v, counter.getOrDefault(v, 0) + 1);
    }
    for (String v : arr) {
      if (counter.get(v) == 1) {
        --k;
        if (k == 0) {
          return v;
        }
      }
    }
    return "";
  }
}

```

### JavaScript

```javascript
/** * @param {string[]} arr * @param {number} k * @return {string} */ var kthDistinct = function ( arr , k ) { const cnt = new Map (); for ( const s of arr ) { cnt . set ( s , ( cnt . get ( s ) || 0 ) + 1 ); } for ( const s of arr ) { if ( cnt . get ( s ) === 1 && -- k === 0 ) { return s ; } } return '' ; };
```

### CPP

```cpp
class Solution {
public:
  string kthDistinct(vector<string> &arr, int k) {
    unordered_map<string, int> counter;
    for (auto &v : arr)
      ++counter[v];
    for (auto &v : arr) {
      if (counter[v] == 1) {
        --k;
        if (k == 0)
          return v;
      }
    }
    return "";
  }
};

```

### Python

```python
class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str: counter = Counter(arr) for v in arr: if counter[v] == 1: k -= 1 if k == 0: return v return ''

```