Skip to main content
Talentd

Find Valid Pair of Adjacent Digits in String - Solution & Explanation

EasyHash TableStringCounting7 min readAsked at: Amazon, Oracle, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given a string of digits, return the first adjacent pair where each digit appears in the entire string exactly as many times as its numeric value. If no such pair exists, return an empty string. The key requirement is verifying global digit frequencies while scanning adjacent characters.

Approach 1: Recount Frequencies for Every Pair (Brute Force) (Time: O(n^2), Space: O(1))

Check every adjacent pair s[i] and s[i+1]. For each pair, scan the entire string and count how many times both digits appear. If the frequency of each digit equals its numeric value and the digits are different, the pair is valid. This approach repeatedly recomputes counts, which leads to quadratic time. It works for very small inputs but scales poorly as the string length grows.

Approach 2: Frequency Counting + Single Pass Scan (Optimal) (Time: O(n), Space: O(1))

First compute digit frequencies using a small hash table or fixed array of size 10. Then iterate through the string once and inspect every adjacent pair. For digits a and b, check two conditions: they must be different, and their frequencies must match their numeric values (freq[a] == int(a) and freq[b] == int(b)). Because digit counts are precomputed, each validation becomes an O(1) lookup. The first pair that satisfies the rule is returned immediately.

This method relies on simple counting combined with constant‑time lookups using a small hash table. The string is scanned only once after counting, making it optimal for large inputs. Since digits are limited to 0–9, memory usage stays constant.

Recommended for interviews: The counting + single pass approach is the expected solution. It demonstrates that you separate global computation (digit frequencies) from local validation (adjacent pairs). Mentioning the brute force approach first shows you understand the naive strategy, while optimizing with precomputed counts and a linear scan shows strong problem‑solving skills with string processing.

Solution

We can use an array cnt of length 10 to record the occurrences of each digit in the string s.

Then, we traverse the adjacent digit pairs in the string s. If the two digits are not equal and the occurrences of these two digits are equal to the digits themselves, we have found a valid pair of adjacent digits and return it.

After traversing, if no valid pair of adjacent digits is found, we return an empty string.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set of the string s. In this problem, \Sigma = {1, 2, ldots, 9}.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recount Frequencies for Each Pair (Brute Force)O(n^2)O(1)Useful for explaining the baseline logic during interviews or when input size is very small.
Frequency Counting + Single ScanO(n)O(1)Best general solution. Precompute counts once and validate adjacent pairs with constant‑time lookups.

Video Solution

100552. Find Valid Pair of Adjacent Digits in String | Strings | Biweekly Contest 149 | Leetcode • Rapid Syntax • 223 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Valid Pair of Adjacent Digits in String easy or hard?
The problem is classified as Easy. It mainly tests basic string traversal and frequency counting. Once you realize that digit counts should be computed once and reused, the implementation becomes a straightforward O(n) solution.
Find Valid Pair of Adjacent Digits in String Python/Java solution
The typical implementation counts digit frequencies using an array or map, then scans adjacent pairs in the string. Python uses a list or Counter, while Java commonly uses an int[10] array. Both implementations achieve O(n) time and O(1) space complexity.
How to solve Find Valid Pair of Adjacent Digits in String in O(n)?
Compute digit frequencies first using a counting array of size 10. Then iterate through the string and examine each adjacent pair s[i] and s[i+1]. If the digits are different and their frequencies equal their numeric values, return that pair. Each check is constant time, producing an overall O(n) algorithm.
What is the best approach for Find Valid Pair of Adjacent Digits in String?
The optimal approach uses frequency counting followed by a single pass over the string. First count how many times each digit appears using a small array or hash map. Then scan adjacent pairs and check whether both digits appear exactly their numeric value times in the string. This runs in O(n) time with O(1) extra space.
Is Find Valid Pair of Adjacent Digits in String asked at Google/Amazon/Meta?
Problems based on frequency counting and string scanning appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of precomputing counts and validating conditions during a linear scan is a common interview technique.
What data structure is used in Find Valid Pair of Adjacent Digits in String?
The main data structure is a small hash table or fixed-size array used for digit frequency counting. Since digits range from 0 to 9, an integer array of size 10 is typically used for constant-time lookups during validation.
What is the time complexity of Find Valid Pair of Adjacent Digits in String?
The optimal solution runs in O(n) time. One pass computes the frequency of each digit, and a second pass checks each adjacent pair. Space complexity is O(1) because there are only 10 possible digits (0–9).

Ready to solve this problem?

Practice Find Valid Pair of Adjacent Digits in String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Contains Duplicate

Next

Majority Element