Problem statement

You are given a string s made only of the digits 1 to 9.

A valid pair is two adjacent characters s[i] and s[i + 1] such that:

• the two digits are different, and
• each of the two digits occurs in the whole of s exactly as many times as its own value (a 3 must occur exactly three times, a 1 exactly once).

Scanning from left to right, return the first valid pair as a two-character string, or an empty string if there is none.

Example 1

Input: s = "4221333"
Output: 21
Explanation: `42` fails (`4` occurs once, not four times), `22` repeats a digit, and `21` works: `2` occurs twice and `1` once.

Example 2

Input: s = "5535"
Output: 
Explanation: `5` occurs three times, not five, and `3` occurs once, not three times, so no pair is valid.

Example 3

Input: s = "22333"
Output: 23

Constraints

• 2 <= s.length <= 100
• s consists only of digits from '1' to '9'

Hints for Find Valid Pair of Adjacent Digits in String

1. Hint 1

   Whether a digit qualifies depends only on how often it occurs in the whole string — count all nine digits first.

2. Hint 2

   Then walk the adjacent pairs from the left and return the first one whose digits differ and both match their counts.

How to solve Find Valid Pair of Adjacent Digits in String

The validity of a digit is a global property (its total count), so one counting pass followed by one scan over adjacent pairs settles it.

Approach

1. Count the occurrences of each digit 1–9.
2. For i from 0 to n - 2, let a = s[i] and b = s[i + 1].
3. If a != b, count[a] == a and count[b] == b, return a followed by b.
4. If no pair qualifies, return the empty string.

Why it works

Both conditions of a valid pair are checked exactly as stated for every adjacent pair in left-to-right order, so the first one returned is the first valid pair, and the empty string is returned only when none exists.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Compare the count with the digit's value, not its character code.
• A pair of equal digits such as 22 never counts, even when 2 occurs exactly twice.

Reference solution

Python

def findValidPair(s: str) -> str:
    count = [0] * 10
    for ch in s:
        count[int(ch)] += 1
    for i in range(len(s) - 1):
        a, b = int(s[i]), int(s[i + 1])
        if a != b and count[a] == a and count[b] == b:
            return s[i:i + 2]
    return ""

Java

public static String findValidPair(String s) {
    int[] count = new int[10];
    for (int i = 0; i < s.length(); i++) count[s.charAt(i) - '0']++;
    for (int i = 0; i + 1 < s.length(); i++) {
        int a = s.charAt(i) - '0', b = s.charAt(i + 1) - '0';
        if (a != b && count[a] == a && count[b] == b) return s.substring(i, i + 2);
    }
    return "";
}

C++

string findValidPair(string s) {
    int count[10] = {0};
    for (char c : s) count[c - '0']++;
    for (int i = 0; i + 1 < (int)s.size(); i++) {
        int a = s[i] - '0', b = s[i + 1] - '0';
        if (a != b && count[a] == a && count[b] == b) return s.substr(i, 2);
    }
    return "";
}

JavaScript

var findValidPair = function(s) {
    var count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for (var i = 0; i < s.length; i++) count[s.charCodeAt(i) - 48]++;
    for (var j = 0; j + 1 < s.length; j++) {
        var a = s.charCodeAt(j) - 48, b = s.charCodeAt(j + 1) - 48;
        if (a !== b && count[a] === a && count[b] === b) return s.substring(j, j + 2);
    }
    return "";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Remove Duplicates from an Unsorted Linked List Easy
• Two Sum IV - Input is a BST Easy