2053. Kth Distinct String in an Array
Approach
Count occurrences with a dictionary; iterate in order and return the kth string with count 1.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
// Approach: Count occurrences with a dictionary; iterate in order and return the kth string with count 1.
// Time: O(n) Space: O(n)
public class Solution
{
public string KthDistinct(string[] arr, int k)
{
Dictionary<string, int> count = new Dictionary<string, int>();
foreach (var a in arr)
count[a] = count.GetValueOrDefault(a, 0) + 1;
foreach (var a in arr)
if (count[a] == 1 && --k == 0)
return a;
return string.Empty;
}
}