Kth Distinct String in an Array - Practice Coding Problems

Kth Distinct String in an Array - 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: The strings are considered in the order in which they appear in the array.

Input & Output

Example 1 — Basic Case

$ Input: arr = ["d","b","c","b","c","a"], k = 2

› Output: "a"

💡 Note: The distinct strings are "d" and "a" (appear only once). The 2nd distinct string is "a".

Example 2 — Not Enough Distinct

$ Input: arr = ["aaa","aa","a"], k = 1

› Output: "aaa"

💡 Note: All strings are distinct (each appears once). The 1st distinct string is "aaa".

Example 3 — No kth Distinct

$ Input: arr = ["a","b","a"], k = 3

› Output: ""

💡 Note: Only "b" is distinct (appears once). Since k=3 but there's only 1 distinct string, return empty string.

Constraints

1 ≤ k ≤ arr.length ≤ 1000
1 ≤ arr[i].length ≤ 5
arr[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with some duplicate strings

Count Frequencies

Identify which strings appear exactly once

Find kth Distinct

Return the kth string with frequency 1

Key Takeaway

🎯 Key Insight: Use frequency counting to identify distinct strings, then iterate in original order to find the kth one

Asked in

a Amazon 25 M Microsoft 18

The key insight is to count the frequency of each string first, then find the kth string that appears exactly once. Best approach uses a hash map for O(n) time counting, then iterates through the original array to maintain order. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count - Two Pass Hash Map	O(n)	O(n)	First pass counts frequencies, second pass finds kth distinct
Brute Force - Count Each String	O(n²)	O(1)	For each string, count its occurrences in the entire array

Frequency Count - Two Pass Hash Map — Algorithm Steps

First pass: Build frequency map of all strings
Second pass: Iterate array and count distinct strings
Return kth distinct string when found

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Build frequency map: d→1, b→2, c→2, a→1

Second Pass

Iterate array, find strings with freq=1

Result

d is 1st distinct, a is 2nd distinct

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STRINGS 1000
#define MAX_LENGTH 100

char* solution(char** arr, int arrSize, int k) {
    // Simple frequency counting using arrays
    char freq_strings[MAX_STRINGS][MAX_LENGTH];
    int freq_counts[MAX_STRINGS];
    int unique_count = 0;
    
    // First pass: count frequencies
    for (int i = 0; i < arrSize; i++) {
        int found = -1;
        for (int j = 0; j < unique_count; j++) {
            if (strcmp(arr[i], freq_strings[j]) == 0) {
                found = j;
                break;
            }
        }
        if (found >= 0) {
            freq_counts[found]++;
        } else {
            strcpy(freq_strings[unique_count], arr[i]);
            freq_counts[unique_count] = 1;
            unique_count++;
        }
    }
    
    // Second pass: find kth distinct
    static char result[MAX_LENGTH];
    int distinctCount = 0;
    
    for (int i = 0; i < arrSize; i++) {
        // Find frequency of current string
        int freq = 0;
        for (int j = 0; j < unique_count; j++) {
            if (strcmp(arr[i], freq_strings[j]) == 0) {
                freq = freq_counts[j];
                break;
            }
        }
        
        if (freq == 1) {
            distinctCount++;
            if (distinctCount == k) {
                strcpy(result, arr[i]);
                return result;
            }
        }
    }
    
    strcpy(result, "");
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array (simplified)
    char** arr = malloc(1000 * sizeof(char*));
    int arrSize = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            arr[arrSize] = malloc(strlen(token) + 1);
            strcpy(arr[arrSize], token);
            arrSize++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    int k;
    scanf("%d", &k);
    
    char* result = solution(arr, arrSize, k);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the array of n elements, hash map operations are O(1)

✓ Linear Growth

Space Complexity

O(n)

Hash map can store up to n unique strings in worst case

⚡ Linearithmic Space

22.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count - Two Pass Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler