algoadvance

Leetcode 2053. Kth Distinct String in an Array

Problem Statement

Given an array of strings arr, and an integer k, return the kth distinct string in the array. If there are fewer than k distinct strings, return an empty string "".

Example 1:

Input: arr = ["d","b","c","b","c","a"], k = 2
Output: "a"
Explanation:
The distinct strings in arr are ["d","b","c","a"].
"b" and "c" are not distinct since they appear more than once.
The 2nd distinct string is "a".

Example 2:

Input: arr = ["aaa","aa","a"], k = 1
Output: "aaa"
Explanation:
All strings in arr are distinct, so the 1st distinct string is "aaa".

Constraints:

Clarifying Questions

  1. Can k be greater than the number of distinct strings in the array?
    • Yes, in such cases, the function should return an empty string "".
  2. Are there any constraints on the length of individual strings?
    • Yes, each string’s length is between 1 and 5 inclusive.
  3. Should the order of distinct strings maintain their first appearance order?
    • Yes, the distinct strings should be considered based on their first occurrence in the array.

Strategy

  1. Use a HashMap to count the frequency of each string in the array.
  2. Iterate through the array to identify distinct strings (strings that have a frequency of 1).
  3. Collect these distinct strings while maintaining the order of their first appearance.
  4. Return the kth distinct string if it exists; otherwise, return an empty string.

Time Complexity

  1. Building the frequency map: O(n), where n is the length of the array.
  2. Collecting distinct strings: O(n).
  3. Overall: O(n) time complexity since both major operations are O(n).

Code

import java.util.HashMap;

public class KthDistinctString {
    public static String kthDistinct(String[] arr, int k) {
        HashMap<String, Integer> frequencyMap = new HashMap<>();
        
        // Step 1: Count the frequency of each string
        for (String str : arr) {
            frequencyMap.put(str, frequencyMap.getOrDefault(str, 0) + 1);
        }
        
        // Step 2: Collect distinct strings
        for (String str : arr) {
            if (frequencyMap.get(str) == 1) {
                k--;
                if (k == 0) {
                    return str;
                }
            }
        }
        
        // If fewer than k distinct strings exist
        return "";
    }
    
    public static void main(String[] args) {
        // Example test cases
        String[] arr1 = {"d","b","c","b","c","a"};
        int k1 = 2;
        System.out.println(kthDistinct(arr1, k1));  // Output: "a"

        String[] arr2 = {"aaa","aa","a"};
        int k2 = 1;
        System.out.println(kthDistinct(arr2, k2));  // Output: "aaa"
        
        String[] arr3 = {"d","b","b","a"};
        int k3 = 2;
        System.out.println(kthDistinct(arr3, k3));  // Output: ""
    }
}

This code will determine the kth distinct string in the given array or return an empty string if the number of distinct strings is less than k.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI