Scale Engineer

Kth Distinct String in an Array

Easy
#1869Time: 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.
Patterns
Counting
Data structures
ArrayHash TableString

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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.

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 "";    }}

Complexity

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.

Trade-offs

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.

Solutions

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 "";  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem