# Find Valid Pair of Adjacent Digits in String
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-valid-pair-of-adjacent-digits-in-string)
Canonical: https://scaleengineer.com/dsa/problems/find-valid-pair-of-adjacent-digits-in-string
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## 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:**

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

# Approaches
## Brute Force with Nested Loops
This approach iterates through all possible adjacent pairs in the string. For each pair, it re-scans the entire string to count the occurrences of both digits to check if they meet the validity criteria. This is a straightforward but inefficient method due to the repeated counting.
**Time:** O(N^2), where N is the length of the string. The outer loop runs N-1 times, and for each iteration, we perform two full scans of the string, each taking O(N) time. · **Space:** O(1), as we only use a few variables for indices and counts, which does not depend on the input size.
**Pros:** Simple to understand and implement as it directly follows the problem's logic.; Requires no additional data structures, leading to minimal O(1) space usage.
**Cons:** Highly inefficient due to redundant computations. The frequency of each digit is recalculated for every potential pair.; The time complexity of O(N^2) can be slow for larger strings, although the problem constraints keep N small.
### Explanation
This method directly translates the problem statement into code without optimization. We iterate from the beginning of the string to the second-to-last character to form adjacent pairs `(s[i], s[i+1])`.

For each pair, we first check the simple condition: are the digits different? If `s[i] == s[i+1]`, we immediately discard the pair and move on. If they are different, we proceed to the more complex frequency check. This involves two separate, full traversals of the entire string: one to count the occurrences of the first digit (`s[i]`) and another to count the occurrences of the second digit (`s[i+1]`).

After getting the counts, we compare them against the numeric values of the digits. If the count of the first digit equals its numeric value, and the same holds for the second digit, we have found our valid pair. Since we are iterating from left to right, the first one we find is the one we need to return. If we iterate through all possible pairs and none satisfy the conditions, we conclude that no valid pair exists and return an empty string.

```java
class Solution {
    public String findValidPair(String s) {
        int n = s.length();
        for (int i = 0; i < n - 1; i++) {
            char d1 = s.charAt(i);
            char d2 = s.charAt(i + 1);

            if (d1 == d2) {
                continue;
            }

            int val1 = d1 - '0';
            int val2 = d2 - '0';

            int count1 = 0;
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == d1) {
                    count1++;
                }
            }

            int count2 = 0;
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == d2) {
                    count2++;
                }
            }

            if (count1 == val1 && count2 == val2) {
                return s.substring(i, i + 2);
            }
        }
        return "";
    }
}
```
### Algorithm
- Loop through the string `s` with an index `i` from `0` to `s.length() - 2`.
- Let `d1 = s.charAt(i)` and `d2 = s.charAt(i + 1)`.
- If `d1` is the same as `d2`, this pair is invalid, so continue to the next `i`.
- If they are different, initialize two counters, `count1` and `count2`, to zero.
- Perform a full scan of the string `s` to count the occurrences of `d1` and store it in `count1`.
- Perform another full scan of the string `s` to count the occurrences of `d2` and store it in `count2`.
- Convert the characters `d1` and `d2` to their numeric values, `val1` and `val2`.
- Check if `count1` equals `val1` AND `count2` equals `val2`.
- If both conditions are met, this is the first valid pair. Return the substring `s.substring(i, i + 2)`.
- If the loop completes without finding a valid pair, return an empty string `""`.

## Optimized Approach with Frequency Map
This approach significantly improves performance by pre-calculating the frequency of each digit in the string. By storing these counts in a map or an array, we avoid the expensive re-computation inside the main loop. We first make a single pass to build the frequency map and then a second pass to check for valid pairs using the stored frequencies.
**Time:** O(N), where N is the length of the string. The first pass to build the frequency map takes O(N), and the second pass to find the pair also takes O(N). The total time is O(N) + O(N) = O(N). · **Space:** O(1), as we use a frequency array of a fixed size (10), which is constant and does not depend on the input string's length.
**Pros:** Optimal time complexity of O(N), making it very efficient.; Avoids redundant calculations by pre-computing frequencies in a single pass.; Maintains simplicity and readability while being performant.
**Cons:** Uses a small amount of extra space for the frequency array, although it's constant space and very minimal.
### Explanation
The key optimization in this approach is to recognize that the frequency of each digit in the string is a fixed property. Instead of re-calculating it repeatedly, we can compute all frequencies once at the beginning.

We start by creating a frequency array, `freq`, of size 10 (for digits 0-9). We then make a single pass through the input string `s`. For each character, we update its count in the `freq` array. This pass takes O(N) time.

With the frequencies pre-computed, we can now find the valid pair efficiently. We perform a second pass through the string, from `i = 0` to `s.length() - 2`, to examine each adjacent pair `(s[i], s[i+1])`. For each pair, we check the three conditions:
1. The digits are not equal (`s[i] != s[i+1]`).
2. The pre-computed frequency of the first digit matches its numeric value (`freq[s[i] - '0'] == s[i] - '0'`).
3. The pre-computed frequency of the second digit matches its numeric value (`freq[s[i+1] - '0'] == s[i+1] - '0'`).

Each of these checks takes constant time. The first pair that satisfies all three conditions is our answer. This two-pass approach reduces the overall time complexity to linear, making it much more efficient.

```java
class Solution {
    public String findValidPair(String s) {
        int[] freq = new int[10];
        for (char c : s.toCharArray()) {
            freq[c - '0']++;
        }

        for (int i = 0; i < s.length() - 1; i++) {
            char d1 = s.charAt(i);
            char d2 = s.charAt(i + 1);

            if (d1 == d2) {
                continue;
            }

            int val1 = d1 - '0';
            int val2 = d2 - '0';

            if (freq[val1] == val1 && freq[val2] == val2) {
                return s.substring(i, i + 2);
            }
        }

        return "";
    }
}
```
### Algorithm
- Create an integer array `freq` of size 10, initialized to all zeros. This will act as our frequency map for digits '0' through '9'.
- Iterate through the input string `s` once. For each character `c`, increment the count in the frequency map: `freq[c - '0']++`.
- After the first pass, `freq` holds the final counts for all digits in `s`.
- Loop through the string `s` again with an index `i` from `0` to `s.length() - 2`.
- Let `d1 = s.charAt(i)` and `d2 = s.charAt(i + 1)`.
- If `d1 == d2`, skip to the next `i`.
- Get the numeric values `val1 = d1 - '0'` and `val2 = d2 - '0'`.
- Check the conditions using the pre-computed frequencies: `freq[val1] == val1` and `freq[val2] == val2`.
- If the conditions are true, this is the first valid pair. Return the substring `s.substring(i, i + 2)`.
- If the loop finishes, return `""`.

# Solutions
### Java

```java
class Solution {
public
  String findValidPair(String s) {
    int[] cnt = new int[10];
    for (char c : s.toCharArray()) {
      ++cnt[c - '0'];
    }
    for (int i = 1; i < s.length(); ++i) {
      int x = s.charAt(i - 1) - '0';
      int y = s.charAt(i) - '0';
      if (x != y && cnt[x] == x && cnt[y] == y) {
        return s.substring(i - 1, i + 1);
      }
    }
    return "";
  }
}

```

### CPP

```cpp
class Solution {
public:
  string findValidPair(string s) {
    int cnt[10]{};
    for (char c : s) {
      ++cnt[c - '0'];
    }
    for (int i = 1; i < s.size(); ++i) {
      int x = s[i - 1] - '0';
      int y = s[i] - '0';
      if (x != y && cnt[x] == x && cnt[y] == y) {
        return s.substr(i - 1, 2);
      }
    }
    return "";
  }
};

```

### Python

```python
class Solution:
    def findValidPair(self, s: str) -> str: cnt = [0] * 10 for x in map(int, s): cnt[x] += 1 for x, y in pairwise(map(int, s)): if x != y and cnt[x] == x and cnt[y] == y: return f " { x }{ y } " return ""

```