Find Valid Pair of Adjacent Digits in String
Source: leetcode
Difficulty: Easy
Tags: hash-table, string, counting

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




C++ solution:
class Solution {
public:
    string findValidPair(string s) {
        int count[10] = {0};
        for (char c : s) {
            count[c - '0']++;
        }
        for (int i = 0; i < s.size() - 1; ++i) {
            char a = s[i], b = s[i+1];
            if (a != b) {
                int a_d = a - '0', b_d = b - '0';
                if (count[a_d] == a_d && count[b_d] == b_d) {
                    return string(1, a) + string(1, b);
                }
            }
        }
        return "";
    }
};

Go solution:
func findValidPair(s string) string {
    freq := make(map[byte]int)
    for i := 0; i < len(s); i++ {
        c := s[i]
        freq[c]++
    }
    for i := 0; i < len(s)-1; i++ {
        a, b := s[i], s[i+1]
        if a != b {
            da, db := int(a-'0'), int(b-'0')
            if freq[a] == da && freq[b] == db {
                return string([]byte{a, b})
            }
        }
    }
    return ""
}

Java solution:
class Solution {
    public String findValidPair(String s) {
        int[] counts = new int[10];
        for (char c : s.toCharArray()) {
            counts[c - '0']++;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            if (a != b && counts[a - '0'] == (a - '0') && counts[b - '0'] == (b - '0')) {
                return "" + a + b;
            }
        }
        return "";
    }
}

JavaScript solution:
var findValidPair = function(s) {
    const freq = {};
    for (const c of s) {
        freq[c] = (freq[c] || 0) + 1;
    }
    for (let i = 0; i < s.length - 1; i++) {
        const a = s[i], b = s[i + 1];
        if (a !== b) {
            const aVal = parseInt(a), bVal = parseInt(b);
            if (freq[a] === aVal && freq[b] === bVal) {
                return a + b;
            }
        }
    }
    return "";
};

Python solution:
class Solution:
    def findValidPair(self, s: str) -> str:
        freq = {}
        for c in s:
            if c in freq:
                freq[c] += 1
            else:
                freq[c] = 1
        for i in range(len(s) - 1):
            a, b = s[i], s[i+1]
            if a != b:
                count_a = freq.get(a, 0)
                count_b = freq.get(b, 0)
                if count_a == int(a) and count_b == int(b):
                    return a + b
        return ""

Ruby solution:
def find_valid_pair(s)
  counts = s.chars.each_with_object(Hash.new(0)) { |c, h| h[c] += 1 }
  (0...s.size-1).each do |i|
    current = s[i]
    next_char = s[i+1]
    if current != next_char
      if counts[current] == current.to_i && counts[next_char] == next_char.to_i
        return current + next_char
      end
    end
  end
  ""
end