3438. Find Valid Pair of Adjacent Digits in String Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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).

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

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

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

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

C++

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

TypeScript

function findValidPair(s: string): string {
    const cnt: number[] = Array(10).fill(0);
    for (const c of s) {
        ++cnt[+c];
    }
    for (let i = 1; i < s.length; ++i) {
        const x = +s[i - 1];
        const y = +s[i];
        if (x !== y && cnt[x] === x && cnt[y] === y) {
            return `${x}${y}`;
        }
    }
    return '';
}

func findValidPair(s string) string {
	cnt := [10]int{}
	for _, c := range s {
		cnt[c-'0']++
	}
	for i := 1; i < len(s); i++ {
		x, y := int(s[i-1]-'0'), int(s[i]-'0')
		if x != y && cnt[x] == x && cnt[y] == y {
			return s[i-1 : i+1]
		}
	}
	return ""
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When 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 Scan	O(n)	O(1)	Best general solution. Precompute counts once and validate adjacent pairs with constant‑time lookups.

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

Find Valid Pair of Adjacent Digits in String solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Find Valid Pair of Adjacent Digits in String solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems