Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Build confidence with an intuition-first walkthrough focused on hash map fundamentals.
You are given a string s consisting only of digits. A valid pair is defined as two adjacent digits in s such that:
s exactly as many times as its numeric value.Return the first valid pair found in the string s when traversing from left to right. If no valid pair exists, return an empty string.
Example 1:
Input: s = "2523533"
Output: "23"
Explanation:
Digit '2' appears 2 times and digit '3' appears 3 times. Each digit in the pair "23" appears in s exactly as many times as its numeric value. Hence, the output is "23".
Example 2:
Input: s = "221"
Output: "21"
Explanation:
Digit '2' appears 2 times and digit '1' appears 1 time. Hence, the output is "21".
Example 3:
Input: s = "22"
Output: ""
Explanation:
There are no valid adjacent pairs.
Constraints:
2 <= s.length <= 100s only consists of digits from '1' to '9'.Problem summary: You are given a string s consisting only of digits. A valid pair is defined as two adjacent digits in s such that: The first digit is not equal to the second. Each digit in the pair appears in s exactly as many times as its numeric value. Return the first valid pair found in the string s when traversing from left to right. If no valid pair exists, return an empty string.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"2523533"
"221"
"22"
majority-element)contains-duplicate)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3438: Find Valid Pair of Adjacent Digits in String
class Solution {
public String findValidPair(String s) {
int[] cnt = new int[10];
for (char c : s.toCharArray()) {
++cnt[c - '0'];
}
for (int i = 1; i < s.length(); ++i) {
int x = s.charAt(i - 1) - '0';
int y = s.charAt(i) - '0';
if (x != y && cnt[x] == x && cnt[y] == y) {
return s.substring(i - 1, i + 1);
}
}
return "";
}
}
// Accepted solution for LeetCode #3438: Find Valid Pair of Adjacent Digits in String
func findValidPair(s string) string {
cnt := [10]int{}
for _, c := range s {
cnt[c-'0']++
}
for i := 1; i < len(s); i++ {
x, y := int(s[i-1]-'0'), int(s[i]-'0')
if x != y && cnt[x] == x && cnt[y] == y {
return s[i-1 : i+1]
}
}
return ""
}
# Accepted solution for LeetCode #3438: Find Valid Pair of Adjacent Digits in String
class Solution:
def findValidPair(self, s: str) -> str:
cnt = [0] * 10
for x in map(int, s):
cnt[x] += 1
for x, y in pairwise(map(int, s)):
if x != y and cnt[x] == x and cnt[y] == y:
return f"{x}{y}"
return ""
// Accepted solution for LeetCode #3438: Find Valid Pair of Adjacent Digits in String
fn find_valid_pair(s: String) -> String {
let bs : Vec<_> = s.bytes().collect();
let mut freq = [0;9];
for &b in &bs {
freq[(b - b'1') as usize] += 1;
}
for (i, w) in bs.windows(2).enumerate() {
if w[0] == w[1] {
continue;
}
let count1 = freq[(w[0] - b'1') as usize];
let count2 = freq[(w[1] - b'1') as usize];
if count1 == w[0] - b'0' && count2 == w[1] - b'0' {
return s[i..(i+2)].to_string();
}
}
"".to_string()
}
fn main() {
let ret = find_valid_pair("2523533".to_string());
println!("ret={ret}");
}
#[test]
fn test()
{
assert_eq!(find_valid_pair("2523533".to_string()), "23");
assert_eq!(find_valid_pair("221".to_string()), "21");
assert_eq!(find_valid_pair("22".to_string()), "");
}
// Accepted solution for LeetCode #3438: Find Valid Pair of Adjacent Digits in String
function findValidPair(s: string): string {
const cnt: number[] = Array(10).fill(0);
for (const c of s) {
++cnt[+c];
}
for (let i = 1; i < s.length; ++i) {
const x = +s[i - 1];
const y = +s[i];
if (x !== y && cnt[x] === x && cnt[y] === y) {
return `${x}${y}`;
}
}
return '';
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.