Find Valid Pair of Adjacent Digits in String
EasyPrompt
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
sexactly 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 <= 100sonly consists of digits from'1'to'9'.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through all possible adjacent pairs in the string. For each pair, it re-scans the entire string to count the occurrences of both digits to check if they meet the validity criteria. This is a straightforward but inefficient method due to the repeated counting.
Algorithm
- Loop through the string
swith an indexifrom0tos.length() - 2. - Let
d1 = s.charAt(i)andd2 = s.charAt(i + 1). - If
d1is the same asd2, this pair is invalid, so continue to the nexti. - If they are different, initialize two counters,
count1andcount2, to zero. - Perform a full scan of the string
sto count the occurrences ofd1and store it incount1. - Perform another full scan of the string
sto count the occurrences ofd2and store it incount2. - Convert the characters
d1andd2to their numeric values,val1andval2. - Check if
count1equalsval1ANDcount2equalsval2. - If both conditions are met, this is the first valid pair. Return the substring
s.substring(i, i + 2). - If the loop completes without finding a valid pair, return an empty string
"".
Walkthrough
This method directly translates the problem statement into code without optimization. We iterate from the beginning of the string to the second-to-last character to form adjacent pairs (s[i], s[i+1]).
For each pair, we first check the simple condition: are the digits different? If s[i] == s[i+1], we immediately discard the pair and move on. If they are different, we proceed to the more complex frequency check. This involves two separate, full traversals of the entire string: one to count the occurrences of the first digit (s[i]) and another to count the occurrences of the second digit (s[i+1]).
After getting the counts, we compare them against the numeric values of the digits. If the count of the first digit equals its numeric value, and the same holds for the second digit, we have found our valid pair. Since we are iterating from left to right, the first one we find is the one we need to return. If we iterate through all possible pairs and none satisfy the conditions, we conclude that no valid pair exists and return an empty string.
class Solution { public String findValidPair(String s) { int n = s.length(); for (int i = 0; i < n - 1; i++) { char d1 = s.charAt(i); char d2 = s.charAt(i + 1); if (d1 == d2) { continue; } int val1 = d1 - '0'; int val2 = d2 - '0'; int count1 = 0; for (int j = 0; j < n; j++) { if (s.charAt(j) == d1) { count1++; } } int count2 = 0; for (int j = 0; j < n; j++) { if (s.charAt(j) == d2) { count2++; } } if (count1 == val1 && count2 == val2) { return s.substring(i, i + 2); } } return ""; }}Complexity
Time
O(N^2), where N is the length of the string. The outer loop runs N-1 times, and for each iteration, we perform two full scans of the string, each taking O(N) time.
Space
O(1), as we only use a few variables for indices and counts, which does not depend on the input size.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem's logic.
Requires no additional data structures, leading to minimal O(1) space usage.
Cons
Highly inefficient due to redundant computations. The frequency of each digit is recalculated for every potential pair.
The time complexity of O(N^2) can be slow for larger strings, although the problem constraints keep N small.
This approach significantly improves performance by pre-calculating the frequency of each digit in the string. By storing these counts in a map or an array, we avoid the expensive re-computation inside the main loop. We first make a single pass to build the frequency map and then a second pass to check for valid pairs using the stored frequencies.
Algorithm
- Create an integer array
freqof size 10, initialized to all zeros. This will act as our frequency map for digits '0' through '9'. - Iterate through the input string
sonce. For each characterc, increment the count in the frequency map:freq[c - '0']++. - After the first pass,
freqholds the final counts for all digits ins. - Loop through the string
sagain with an indexifrom0tos.length() - 2. - Let
d1 = s.charAt(i)andd2 = s.charAt(i + 1). - If
d1 == d2, skip to the nexti. - Get the numeric values
val1 = d1 - '0'andval2 = d2 - '0'. - Check the conditions using the pre-computed frequencies:
freq[val1] == val1andfreq[val2] == val2. - If the conditions are true, this is the first valid pair. Return the substring
s.substring(i, i + 2). - If the loop finishes, return
"".
Walkthrough
The key optimization in this approach is to recognize that the frequency of each digit in the string is a fixed property. Instead of re-calculating it repeatedly, we can compute all frequencies once at the beginning.
We start by creating a frequency array, freq, of size 10 (for digits 0-9). We then make a single pass through the input string s. For each character, we update its count in the freq array. This pass takes O(N) time.
With the frequencies pre-computed, we can now find the valid pair efficiently. We perform a second pass through the string, from i = 0 to s.length() - 2, to examine each adjacent pair (s[i], s[i+1]). For each pair, we check the three conditions:
- The digits are not equal (
s[i] != s[i+1]). - The pre-computed frequency of the first digit matches its numeric value (
freq[s[i] - '0'] == s[i] - '0'). - The pre-computed frequency of the second digit matches its numeric value (
freq[s[i+1] - '0'] == s[i+1] - '0').
Each of these checks takes constant time. The first pair that satisfies all three conditions is our answer. This two-pass approach reduces the overall time complexity to linear, making it much more efficient.
class Solution { public String findValidPair(String s) { int[] freq = new int[10]; for (char c : s.toCharArray()) { freq[c - '0']++; } for (int i = 0; i < s.length() - 1; i++) { char d1 = s.charAt(i); char d2 = s.charAt(i + 1); if (d1 == d2) { continue; } int val1 = d1 - '0'; int val2 = d2 - '0'; if (freq[val1] == val1 && freq[val2] == val2) { return s.substring(i, i + 2); } } return ""; }}Complexity
Time
O(N), where N is the length of the string. The first pass to build the frequency map takes O(N), and the second pass to find the pair also takes O(N). The total time is O(N) + O(N) = O(N).
Space
O(1), as we use a frequency array of a fixed size (10), which is constant and does not depend on the input string's length.
Trade-offs
Pros
Optimal time complexity of O(N), making it very efficient.
Avoids redundant calculations by pre-computing frequencies in a single pass.
Maintains simplicity and readability while being performant.
Cons
Uses a small amount of extra space for the frequency array, although it's constant space and very minimal.
Solutions
Solution
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 ""; }}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 ""; }};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 ""Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.