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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4

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:

1
2
3
4

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 "".

Solution

Video Explanation

Here is the video explanation covering the below methods:

Method 1 - Brute Force

  1. Count Occurrences to check duplicates: Use a helper function or nested loops to count the occurrences of each string.

  2. Identify and Return the k-th Distinct String:

    • Iterate through the array again, counting the distinct strings directly.
    • Return the k-th distinct string once found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {

	private boolean isDuplicate(String[] arr, String target) {
		int count = 0;

		for (String str: arr) {
			if (str.equals(target)) {
				count++;
			}
			if (count > 1) {
				return true;
			}
		}

		return false;
	}

	public String kthDistinct(String[] arr, int k) {
		int distinctCount = 0;

		for (String str: arr) {
			if (!isDuplicate(arr, str)) {
				distinctCount++;

				if (distinctCount == k) {
					return str;
				}
			}
		}

		return "";
	}

}

Complexity

  • ⏰ Time complexity: O(n^2) where n is the number of elements in arr
  • 🧺 Space complexity: O(1)

Method 2 - Using Frequency Map

To solve this problem, we can follow these steps:

  1. Count the frequency of each string in the array using a hashmap (dictionary).
  2. Iterate through the array in the given order and identify the distinct strings (strings that appear exactly once in the array).
  3. Keep track of the distinct strings and return the k-th distinct string if it exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {

	public String kthDistinct(String[] arr, int k) {
		// Step 1: Count the frequency of each string
		Map<String, Integer> frequencyMap = new HashMap<>();

		for (String str: arr) {
			frequencyMap.put(str, frequencyMap.getOrDefault(str, 0) + 1);
		}

		// Step 2: Identify distinct strings and find the k-th one
		int count = 0;

		for (String str: arr) {
			if (frequencyMap.get(str) == 1) {
				count++;

				if (count == k) {
					return str;
				}
			}
		}

		// Step 3: If there are fewer than k distinct strings, return ""
		return "";
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def kth_distinct(arr: List[str], k: int) -> str:
    unique_elements = OrderedDict()
    duplicates = set()

    for elem in arr:
        if elem in duplicates:
            continue
        if elem in unique_elements:
            del unique_elements[elem]
            duplicates.add(elem)
        else:
            unique_elements[elem] = None

    if len(unique_elements) < k:
        return ""

    for idx, key in enumerate(unique_elements):
        if idx == k - 1:
            return key

    return ""

Complexity

  • ⏰ Time complexity: O(n) where n is the number of elements in arr
  • 🧺 Space complexity: O(n)

Method 3 - Using LinkedHashSet for order preservation

We can use LinkedHashSet instead.

  1. Use a LinkedHashSet to store all distinct elements (elements that have not been seen before).
  2. Use a HashSet to keep track of elements that have already been seen more than once.
  3. Iterate through the array and perform the checks and insertions accordingly.
  4. Finally, retrieve the k-th distinct element from the LinkedHashSet.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {

	public String kthDistinct(String[] arr, int k) {
		LinkedHashSet<String> distincts = new LinkedHashSet<>();
		HashSet<String> duplicates = new HashSet<>();

		for (String str: arr) {
			if (!duplicates.contains(str)) {
				if (!distincts.contains(str)) {
					distincts.add(str);
				} else {
					distincts.remove(str);
					duplicates.add(str);
				}
			}
		}

		if (distincts.size()<k) {
			return "";
		}

		Iterator<String> iterator = distincts.iterator();

		int count = 0;

		while (iterator.hasNext()) {
			count++;
			String element = iterator.next();

			if (count == k) {
				return element;
			}
		}

		return "";
	}
}

Complexity

  • ⏰ Time complexity: O(n + k), where k is element provided in the function
  • 🧺 Space complexity: O(n)