problemeasyalgorithmsleetcode-3438leetcode 3438leetcode3438

Find Valid Pair of Adjacent Digits in String

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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.

Examples

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 <= 100
  • s only consists of digits from '1' to '9'.

Solution

Method 1 – Frequency Counting and Pair Scan

Intuition

We count the frequency of each digit in the string, then scan for the first adjacent pair of different digits where each digit appears in the string exactly as many times as its numeric value.

Approach

  1. Count the frequency of each digit in the string.
  2. Iterate through the string from left to right:
    • For each adjacent pair (s[i], s[i+1]), check:
      • The digits are different.
      • The count of s[i] equals int(s[i]).
      • The count of s[i+1] equals int(s[i+1]).
    • If so, return the pair as a string.
  3. If no valid pair is found, return an empty string.

Code

C++
class Solution {
public:
    string findValidPair(string s) {
        vector<int> cnt(10, 0);
        for (char c : s) cnt[c - '0']++;
        for (int i = 0; i + 1 < s.size(); ++i) {
            int a = s[i] - '0', b = s[i+1] - '0';
            if (a != b && cnt[a] == a && cnt[b] == b)
                return string(1, s[i]) + s[i+1];
        }
        return "";
    }
};
Go
func findValidPair(s string) string {
    cnt := make([]int, 10)
    for _, c := range s {
        cnt[c-'0']++
    }
    for i := 0; i+1 < len(s); i++ {
        a, b := s[i]-'0', s[i+1]-'0'
        if a != b && cnt[a] == int(a) && cnt[b] == int(b) {
            return s[i:i+2]
        }
    }
    return ""
}
Java
class Solution {
    public String findValidPair(String s) {
        int[] cnt = new int[10];
        for (char c : s.toCharArray()) cnt[c - '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 && cnt[a] == a && cnt[b] == b)
                return s.substring(i, i+2);
        }
        return "";
    }
}
Kotlin
class Solution {
    fun findValidPair(s: String): String {
        val cnt = IntArray(10)
        for (c in s) cnt[c - '0']++
        for (i in 0 until s.length - 1) {
            val a = s[i] - '0'
            val b = s[i+1] - '0'
            if (a != b && cnt[a] == a && cnt[b] == b)
                return s.substring(i, i+2)
        }
        return ""
    }
}
Python
class Solution:
    def findValidPair(self, s: str) -> str:
        from collections import Counter
        cnt = Counter(s)
        for i in range(len(s)-1):
            a, b = s[i], s[i+1]
            if a != b and cnt[a] == int(a) and cnt[b] == int(b):
                return a + b
        return ""
Rust
impl Solution {
    pub fn find_valid_pair(s: String) -> String {
        let mut cnt = [0; 10];
        for c in s.chars() {
            cnt[c as usize - '0' as usize] += 1;
        }
        let s_bytes = s.as_bytes();
        for i in 0..s_bytes.len()-1 {
            let a = (s_bytes[i] - b'0') as usize;
            let b = (s_bytes[i+1] - b'0') as usize;
            if a != b && cnt[a] == a && cnt[b] == b {
                return s[i..i+2].to_string();
            }
        }
        String::new()
    }
}
TypeScript
class Solution {
    findValidPair(s: string): string {
        const cnt = Array(10).fill(0);
        for (const c of s) cnt[+c]++;
        for (let i = 0; i + 1 < s.length; i++) {
            const a = +s[i], b = +s[i+1];
            if (a !== b && cnt[a] === a && cnt[b] === b)
                return s[i] + s[i+1];
        }
        return "";
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, since we count and scan once.
  • 🧺 Space complexity: O(1), since digit counts are bounded by 10.

Comments