# 2053. Kth Distinct String in an Array

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* `kᵗʰ` ***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.

### Thoughts

* Definitely something with a hash table or map
    
* ordering is important here to get the kth distinct
    
* java's `LinkedHashMap` might be a good solution here as it is a hash map which allows for faster checking of duplicates via `contains()` while also maintaining the ordering of the elements
    
    * googled and found that there is a `LinkedHashSet` as well, which is more applicable here since there is no need for storing any value
        
    * Problem with this solution is actually getting the kth entry, neither of these classes provide methods allowing for getting arbitrary indices
        
        * `LinkedHashSet` has `forEach()` which could be hacked together to get the correct entry I think
            
            * can't break out of a lambda function, so `forEach()` might not be the solution here
                
            * can just set a temp variable equal to the correct index, the problem is that there is the problem of atomicity due to it being a lambda, although an `AtomicReference` would fix this
                
            * I make my life unnecessarily hard sometimes by doing things in silly ways
                
                * (Also had to use `AtomicInteger` so that my temp variable worked)
                    
    * First solution:
        
        * ```java
                  class Solution {
                      public String kthDistinct(String[] arr, int k) {
                          LinkedHashSet<String> lhs = new LinkedHashSet();
                          for (String s : arr) {
                              if (!lhs.add(s)) {
                                  lhs.remove(s);
                              }
                          }
                  
                          AtomicInteger i = new AtomicInteger(1);
                          AtomicReference<String> temp = new AtomicReference("");
                          lhs.forEach(s -> {
                              System.out.println(s);
                              if (i.intValue() == k) {
                                  temp.set(s);
                              }
                              i.set(i.get() + 1);
                          });
                  
                          return temp.toString();
                      }
                  }
            ```
            
        * turns out this solution is flawed, as it allows for readding of duplicate entries back to the `LinkedHashSet` (ty ceru &lt;3)
            
            * Ended up just adding another `LinkedHashSet` to it to contain duplicates, which I am pretty sure is not the optimal solution
                

### Solution

```java
class Solution {
    public String kthDistinct(String[] arr, int k) {
        LinkedHashSet<String> lhs = new LinkedHashSet();
        LinkedHashSet<String> olhs = new LinkedHashSet();
           
        // Iterate through arr, adding them to lhs if not a duplicate, olhs if they are        
        for (String s : arr) {
            if (olhs.contains(s) || !lhs.add(s)) {
                lhs.remove(s);
                olhs.add(s);
            }
        }

        // Using AtomicReferences here because of the lambda
        AtomicInteger i = new AtomicInteger(1);
        AtomicReference<String> temp = new AtomicReference("");
        lhs.forEach(s -> {
            // Iterate through all of the distinct values until finding the correct index
            if (i.intValue() == k) {
                temp.set(s);
            }
            i.set(i.get() + 1);
        });

        return temp.toString();
    }
}
```

**Time Complexity:** O(n)  
**Space Complexity:** O(n)

### Conclusion

Overall this one was relatively easy once I determined how I wanted to go about it. I had to reference the Javadocs for both `LinkedHashSet` and `AtomicReference`/`AtomicInteger` as I had forgotten the specifics of how they worked. I am also pretty sure that there is a better solution than using two `LinkedHashSet`, perhaps using just a `LinkedHashMap` instead and using the values to keep track of duplicates. It also took me a while to figure out exactly how I wanted to go about this solving this problem, I think with more practice though, this should get better.