LeetCode 3438 - Find Valid Pair of Adjacent Digits in String
The problem gives us a string s containing only digits from '1' to '9'. We need to find the first adjacent pair of digits that satisfies two conditions. First, the two digits in the pair must be different. A pair like "22" or "55" is never valid.
Difficulty: š¢ Easy
Topics: Hash Table, String, Counting
Solution
Problem Understanding
The problem gives us a string s containing only digits from '1' to '9'. We need to find the first adjacent pair of digits that satisfies two conditions.
First, the two digits in the pair must be different. A pair like "22" or "55" is never valid.
Second, each digit in the pair must appear in the entire string exactly as many times as its numeric value. For example, digit '2' is valid only if '2' appears exactly 2 times in the whole string. Similarly, digit '3' is valid only if '3' appears exactly 3 times in the whole string.
The task is to scan the string from left to right and return the first adjacent pair that satisfies both requirements. If no such pair exists, we return an empty string.
For example, in "2523533":
'2'appears exactly 2 times.'3'appears exactly 3 times.
When we encounter the adjacent pair "23", both digits satisfy the frequency requirement and the digits are different, so "23" is returned.
The constraints are very small:
2 <= s.length <= 100- Digits are only
'1'through'9'
Because the string length is at most 100, almost any reasonable solution will run comfortably within limits. However, it is still useful to design the cleanest and most efficient approach.
Several edge cases are important:
- A pair may contain identical digits, which must be rejected.
- A digit may appear more or fewer times than its value, which invalidates the pair.
- Multiple valid pairs may exist, but only the first one from left to right should be returned.
- The string may contain no valid pair at all, requiring an empty string result.
- Since digits are limited to
'1'through'9', converting a character to its numeric value is straightforward.
Approaches
Brute Force
A straightforward approach is to examine every adjacent pair in the string. For each pair, we can recount the occurrences of both digits by scanning the entire string.
For a pair at positions i and i+1, we would:
- Check whether the digits are different.
- Count how many times the first digit appears in the whole string.
- Count how many times the second digit appears in the whole string.
- Compare those counts against the numeric values of the digits.
If both conditions hold, we return the pair immediately.
This approach is correct because it directly checks the definition of a valid pair. However, it repeatedly recomputes frequencies for the same digits. Since there are up to n-1 pairs and each frequency calculation may scan the entire string, the work is unnecessarily repeated.
Optimal Approach
The key observation is that digit frequencies are properties of the entire string and do not change while we inspect different pairs.
Therefore, we should compute all digit frequencies once at the beginning using a hash map (dictionary). After that, each adjacent pair can be validated in constant time:
- Verify the digits are different.
- Look up the frequency of each digit in the hash map.
- Compare each frequency with the digit's numeric value.
Since frequency lookup is constant time, the entire scan becomes linear.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(nĀ²) | O(1) | Recounts frequencies for every adjacent pair |
| Optimal | O(n) | O(1) | Precomputes frequencies once, then scans pairs |
The space complexity of the optimal solution is technically O(1) because there are only 9 possible digits ('1' through '9'), so the frequency table never grows beyond a constant size.
Algorithm Walkthrough
- Create a hash map that stores the frequency of every digit in the string. This allows us to answer frequency queries in constant time instead of repeatedly scanning the string.
- Traverse the string from left to right, considering every adjacent pair
s[i]ands[i+1]. - For each pair, first check whether the two digits are different. If they are the same, the pair cannot be valid and we move to the next position.
- Convert each digit character into its numeric value. For example,
'3'becomes3. - Use the frequency map to determine how many times each digit appears in the entire string.
- Check whether the frequency of the first digit equals its numeric value and whether the frequency of the second digit equals its numeric value.
- If both checks succeed, return the two-character substring immediately. Because we scan from left to right, the first valid pair encountered is exactly the one required by the problem.
- If the scan completes without finding a valid pair, return an empty string.
Why it works
The frequency map contains the exact occurrence count of every digit in the string. For each adjacent pair, we directly verify the two conditions from the problem statement:
- The digits are different.
- Each digit appears exactly as many times as its numeric value.
Every pair is examined in left-to-right order. Therefore, the first pair that passes these checks is precisely the first valid pair required by the problem. If no pair passes, then no valid pair exists and returning an empty string is correct.
Python Solution
class Solution:
def findValidPair(self, s: str) -> str:
frequency = {}
for digit in s:
frequency[digit] = frequency.get(digit, 0) + 1
for i in range(len(s) - 1):
first = s[i]
second = s[i + 1]
if first == second:
continue
if (
frequency[first] == int(first)
and frequency[second] == int(second)
):
return first + second
return ""
The implementation begins by building a frequency dictionary for all digits in the string. This preprocessing step ensures that later frequency checks are constant time operations.
Next, the code scans every adjacent pair. If both characters are identical, the pair is immediately skipped because the problem requires different digits.
For pairs containing different digits, the code compares the stored frequency of each digit against its numeric value obtained with int(). If both comparisons succeed, the pair is returned immediately.
If the loop finishes without finding a valid pair, the function returns an empty string, indicating that no valid adjacent pair exists.
Go Solution
func findValidPair(s string) string {
frequency := make(map[byte]int)
for i := 0; i < len(s); i++ {
frequency[s[i]]++
}
for i := 0; i < len(s)-1; i++ {
first := s[i]
second := s[i+1]
if first == second {
continue
}
if frequency[first] == int(first-'0') &&
frequency[second] == int(second-'0') {
return s[i : i+2]
}
}
return ""
}
The Go implementation follows exactly the same logic as the Python version. A map[byte]int is used to store frequencies because the string consists only of ASCII digit characters.
Instead of int(first), Go converts a digit character to its numeric value using first - '0'. The returned pair is obtained through string slicing with s[i:i+2].
No special handling for integer overflow is required because frequencies are at most 100.
Worked Examples
Example 1
Input: s = "2523533"
Frequency Map
| Digit | Frequency |
|---|---|
| 2 | 2 |
| 5 | 2 |
| 3 | 3 |
Scan Adjacent Pairs
| Index | Pair | Different? | Frequency Check | Result |
|---|---|---|---|---|
| 0 | 25 | Yes | 2ā2 , 5ā2 |
Invalid |
| 1 | 52 | Yes | 5ā2 |
Invalid |
| 2 | 23 | Yes | 2ā2 , 3ā3 |
Return "23" |
Output:
"23"
Example 2
Input: s = "221"
Frequency Map
| Digit | Frequency |
|---|---|
| 2 | 2 |
| 1 | 1 |
Scan Adjacent Pairs
| Index | Pair | Different? | Frequency Check | Result |
|---|---|---|---|---|
| 0 | 22 | No | Not checked | Invalid |
| 1 | 21 | Yes | 2ā2 , 1ā1 |
Return "21" |
Output:
"21"
Example 3
Input: s = "22"
Frequency Map
| Digit | Frequency |
|---|---|
| 2 | 2 |
Scan Adjacent Pairs
| Index | Pair | Different? | Result |
|---|---|---|---|
| 0 | 22 | No | Invalid |
No valid pair is found.
Output:
""
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | One pass to count frequencies and one pass to scan pairs |
| Space | O(1) | At most 9 distinct digit entries are stored |
The algorithm performs two linear traversals of the string. The first computes frequencies, and the second checks adjacent pairs. Since only digits '1' through '9' can appear, the frequency table has a fixed maximum size, making the auxiliary space constant.
Test Cases
sol = Solution()
assert sol.findValidPair("2523533") == "23" # example 1
assert sol.findValidPair("221") == "21" # example 2
assert sol.findValidPair("22") == "" # example 3
assert sol.findValidPair("12") == "" # neither digit frequency matches value
assert sol.findValidPair("122333") == "12" # first pair already valid
assert sol.findValidPair("212") == "21" # multiple valid pairs, return first
assert sol.findValidPair("111") == "" # frequency of 1 is incorrect
assert sol.findValidPair("121") == "12" # both digits satisfy counts
assert sol.findValidPair("333222") == "" # only identical adjacent digits
assert sol.findValidPair("1223334444") == "12" # several valid digits, first pair wins
assert sol.findValidPair("33221") == "21" # valid pair appears near end
assert sol.findValidPair("123") == "" # no digit has matching frequency
assert sol.findValidPair("4444") == "" # identical digits only
assert sol.findValidPair("221333") == "21" # valid pair after repeated digits
Test Summary
| Test | Why |
|---|---|
"2523533" |
Official example with valid pair in the middle |
"221" |
Official example with valid pair near the end |
"22" |
Official example with no valid pair |
"12" |
Frequencies do not match digit values |
"122333" |
First adjacent pair is valid |
"212" |
Multiple candidate pairs, first must be returned |
"111" |
Single digit frequency mismatch |
"121" |
Small valid input |
"333222" |
All adjacent pairs use equal digits |
"1223334444" |
Several digits satisfy frequency requirements |
"33221" |
Valid pair appears late in traversal |
"123" |
No digit has correct frequency |
"4444" |
Repeated identical digit only |
"221333" |
Valid pair after an invalid repeated pair |
Edge Cases
Adjacent Digits Are Equal
A common mistake is to only check frequency requirements and forget that the two digits must be different. For example, in "22", digit '2' appears exactly twice, but the pair "22" is still invalid because both characters are the same. The implementation explicitly checks first == second and skips such pairs.
Multiple Valid Pairs Exist
Consider "212". Both "21" and "12" satisfy the frequency requirements. The problem asks for the first valid pair encountered while traversing left to right. Since the algorithm scans pairs in order and immediately returns upon finding a valid one, it correctly returns "21".
Digits Have Incorrect Frequencies
A pair may contain different digits but still fail because one or both frequencies do not match the digit values. For example, in "12", digit '1' appears once, but digit '2' appears only once instead of twice. The implementation checks both frequency conditions independently, ensuring that such pairs are rejected.
No Valid Pair Exists
Some inputs contain no valid pair at all, such as "123" or "22". After examining every adjacent pair, the algorithm reaches the end of the loop and returns an empty string. This guarantees the correct behavior when no solution exists.
Valid Pair Appears Late in the String
A valid pair may not occur until the final few positions. For example, "33221" returns "21". Since the algorithm examines every adjacent pair in order and only returns when a valid pair is found, late-occurring solutions are handled correctly.