algoadvance

Leetcode 2053. Kth Distinct String in an Array

Problem Statement

  1. Kth Distinct String in an Array

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

A distinct string is a string that appears only once in the array.

Clarifying Questions

  1. What is the size of the array?
    • The length of arr can vary, but for the problem constraints, assume it can be up to 1000.
  2. What kind of characters can the strings contain?
    • The strings will contain only lowercase English letters.
  3. What should be the result if k is greater than the number of distinct strings?
    • The result should be an empty string as per the problem statement.
  4. Is k guaranteed to be a positive integer?
    • Yes, based on the problem statement.
  5. Will there be any empty strings in the array?
    • No explicit constraints are given, assume no empty strings unless stated otherwise.

Strategy

  1. Count the Frequency of Each String:
    • Use a hash map (unordered_map in C++) to count how many times each string appears in the array.
  2. Identify Distinct Strings:
    • Traverse the array and use the hash map to collect strings that appear exactly once.
  3. Find the k-th Distinct String:
    • Maintain a counter for distinct strings and return the k-th one based on this counter.

Code

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

std::string kthDistinct(std::vector<std::string>& arr, int k) {
    std::unordered_map<std::string, int> frequency;

    // Counting the frequency of each string in the array
    for (const std::string &str : arr) {
        frequency[str]++;
    }

    // Finding the k-th distinct string
    int distinct_count = 0;
    for (const std::string &str : arr) {
        if (frequency[str] == 1) {
            ++distinct_count;
            if (distinct_count == k) {
                return str;
            }
        }
    }

    // If there are fewer than k distinct strings
    return "";
}

int main() {
    std::vector<std::string> arr = {"a", "b", "a", "c", "b", "d"};
    int k = 2;

    std::string result = kthDistinct(arr, k);
    std::cout << "The " << k << "-th distinct string is: " << result << std::endl;

    return 0;
}

Time Complexity

  1. Counting Frequencies:
    • This step involves iterating over the array once to count the occurrences of each string.
    • Time complexity: O(n), where n is the number of strings in the array.
  2. Finding the k-th Distinct String:
    • This step involves iterating over the array again to find the k-th distinct string.
    • Time complexity: O(n), where n is the number of strings in the array.

Thus, the overall time complexity is O(n).

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