Find Valid Pair of Adjacent Digits in String

Find Valid Pair of Adjacent Digits in String

1. What is this problem about?

The Find Valid Pair of Adjacent Digits in String interview question is a string validation task. You are given a numeric string. A "valid pair" consists of two adjacent characters s[i] and s[i+1] such that:

1. The two digits are different ($s[i] eq s[i+1]$).
2. The frequency of digit $s[i]$ in the entire string is exactly equal to its numeric value.
3. The frequency of digit $s[i+1]$ in the entire string is exactly equal to its numeric value. You need to return the first such pair encountered in the string.

2. Why is this asked in interviews?

Amazon and Oracle ask the Find Valid Pair coding problem to assess a candidate's ability to combine global information (frequency counting) with local constraints (adjacent pairs). It evaluations your proficiency with Hash Table interview patterns and your ability to write clean, linear-time code.

3. Algorithmic pattern used

This problem follows the Frequency Counting and Linear Scan pattern.

1. Global Count: Iterate through the string once and store the frequency of each digit ('0'-'9') in a frequency array or hash map.
2. Pair Validation: Iterate through the string again from index 0 to $n-2$.
3. Check Condition: For each adjacent pair:
   • Check if the two digits are different.
   • Check if freq[s[i]] == int(s[i]).
   • Check if freq[s[i+1]] == int(s[i+1]).
4. Result: Return the first pair that satisfies all three conditions.

4. Example explanation

String: "221333"

• Counts: 2: 2, 1: 1, 3: 3.
• Pair (2, 2) at index 0: Digits are the same. Invalid.
• Pair (2, 1) at index 1:
  • $2 eq 1$. (OK)
  • freq[2] is 2. (OK)
  • freq[1] is 1. (OK) Result: "21".

5. Common mistakes candidates make

• One-pass attempt: Trying to find the pair before the full frequency map is built.
• Integer Conversion: Forgetting to convert the character '2' to the integer 2 for the frequency comparison.
• Tie-breaking: Not returning the first pair found in the string.

6. Interview preparation tip

Always use a two-pass approach for problems that depend on global counts. Pass 1 builds the "context" (frequencies), and Pass 2 applies the rules based on that context. This is a standard and robust String interview pattern.