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:

    •         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 <3)

      • Ended up just adding another LinkedHashSet to it to contain duplicates, which I am pretty sure is not the optimal solution

Solution

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.