Find Valid Pair of Adjacent Digits in String

Problem Description

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.

Key Insights

• The digits in the string range from '1' to '9', allowing us to count their occurrences easily.
• We need to check each adjacent pair of digits for validity based on the defined conditions.
• A hash table (or dictionary) will be useful for counting the occurrences of each digit.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, as we traverse the string and check pairs. Space Complexity: O(1), since we only use a fixed-size array to count digits (maximum size of 9).

Solution

To solve the problem, we can use the following approach:

1. Create an array to count occurrences of each digit from '1' to '9'.
2. Traverse the string to populate the count array.
3. Iterate through the string again to check each adjacent pair of digits:
   • Ensure the digits are not equal.
   • Check if each digit's count matches its numeric value.
4. Return the first valid pair found or an empty string if none exists.

Code Solutions