#3438

Easy

LeetCode Problem Workspace

Find Valid Pair of Adjacent Digits in String

Identify the first valid adjacent digit pair in a string where each digit appears exactly as many times as its numeric value using a hash table.

hash table string counting

Problem Statement

Given a string s composed only of digits '1' through '9', identify the first pair of adjacent digits such that each digit occurs in the string exactly as many times as its numeric value. If multiple pairs satisfy the condition, return the first found from left to right.

For example, in s = "2523533", the pair "23" is valid because digit '2' appears 2 times and digit '3' appears 3 times. If no valid pair exists, return an empty string.

Examples

Example 1

Input: s = "2523533"

Output: "23"

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"

Digit '2' appears 2 times and digit '1' appears 1 time. Hence, the output is "21" .

Example 3

Input: s = "22"

Output: ""

There are no valid adjacent pairs.

Constraints

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

Solution Approach

Count Digit Frequencies

Use a hash table to count the number of times each digit appears in the string. This ensures quick lookup to verify if a digit's frequency matches its numeric value.

Check Adjacent Pairs

Iterate through the string, examining each adjacent pair. For each pair, check if both digits' counts match their numeric values using the hash table from the previous step.

Return the First Valid Pair

As soon as a pair satisfies the condition, return it immediately. If the iteration completes with no valid pair found, return an empty string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for counting plus O(n) for scanning adjacent pairs, yielding overall O(n). Space complexity is O(1) since the hash table only stores counts for digits '1' through '9'.

What Interviewers Usually Probe

Does the candidate correctly handle counting digit occurrences with a hash table?
Does the candidate correctly check every adjacent pair without skipping potential valid pairs?
Is the solution efficient in both time and space considering the small fixed digit set?

Common Pitfalls or Variants

Common pitfalls

Ignoring that only digits '1' through '9' are valid and counting '0' can lead to errors.
Failing to return the first valid pair and instead returning the last or all pairs.
Recomputing counts for each pair instead of precomputing frequencies using a hash table.

Follow-up variants

Find all valid adjacent pairs instead of just the first one.
Allow the string to include '0' and adjust the counting condition accordingly.
Find valid triplets of digits where each digit's frequency equals its numeric value.

FAQ

What defines a valid pair in Find Valid Pair of Adjacent Digits in String?

A valid pair consists of two adjacent digits where each digit occurs in the string exactly as many times as its numeric value.

Can zeros appear in the string for this problem?

No, the string only contains digits '1' through '9'. Including '0' would violate the problem constraints.

What is the best approach to solve this problem efficiently?

Use a hash table to count the frequency of each digit and then scan each adjacent pair to find the first valid one.

What should be returned if no valid adjacent pair exists?

Return an empty string if no pair satisfies the frequency condition.

Does the Hash Table plus String pattern always guarantee O(n) performance?

Yes, because counting digits is O(n) and checking adjacent pairs is O(n), giving an overall linear time solution.

terminal

Solution

Solution 1: Counting

We can use an array $\textit{cnt}$ of length $10$ to record the occurrences of each digit in the string $\textit{s}$.

1

2

3

4

5

6

7

8

9

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 ""

Continue Practicing

#3442 maximum difference between even and odd frequency i #3443 maximum manhattan distance after k changes #3389 minimum operations to make character frequencies equal