Find Valid Pair of Adjacent Digits in String - Solution & Explanation

Problem Overview: Given a string of digits, return the first adjacent pair where each digit appears in the entire string exactly as many times as its numeric value. If no such pair exists, return an empty string. The key requirement is verifying global digit frequencies while scanning adjacent characters.

Approach 1: Recount Frequencies for Every Pair (Brute Force) (Time: O(n^2), Space: O(1))

Check every adjacent pair s[i] and s[i+1]. For each pair, scan the entire string and count how many times both digits appear. If the frequency of each digit equals its numeric value and the digits are different, the pair is valid. This approach repeatedly recomputes counts, which leads to quadratic time. It works for very small inputs but scales poorly as the string length grows.

Approach 2: Frequency Counting + Single Pass Scan (Optimal) (Time: O(n), Space: O(1))

First compute digit frequencies using a small hash table or fixed array of size 10. Then iterate through the string once and inspect every adjacent pair. For digits a and b, check two conditions: they must be different, and their frequencies must match their numeric values (freq[a] == int(a) and freq[b] == int(b)). Because digit counts are precomputed, each validation becomes an O(1) lookup. The first pair that satisfies the rule is returned immediately.

This method relies on simple counting combined with constant‑time lookups using a small hash table. The string is scanned only once after counting, making it optimal for large inputs. Since digits are limited to 0–9, memory usage stays constant.

Recommended for interviews: The counting + single pass approach is the expected solution. It demonstrates that you separate global computation (digit frequencies) from local validation (adjacent pairs). Mentioning the brute force approach first shows you understand the naive strategy, while optimizing with precomputed counts and a linear scan shows strong problem‑solving skills with string processing.