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.

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

Input: s = "221"
Output: "21"
Explanation:
Digit `'2'` appears 2 times and digit `'1'` appears 1 time. Hence, the output
is `"21"`.

Example 3

1
2
3
4

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'.

Examples

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 ""
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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 "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 ""
    }
}
1
2
3
4
5
6
7
8
9

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 ""
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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.