3438. Find Valid Pair of Adjacent Digits in String

EasyHash TableStringCounting

Problem Description

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.

Intuition

The solution involves identifying pairs of adjacent digits within the string s where specific criteria are met. To tackle this problem, we need to focus on these steps:

Count Occurrences: Begin by counting how often each digit from 0 to 9 appears in the string s. This will help in determining if a digit appears exactly as many times as its numeric value.
Pairwise Comparison: As we traverse the string s, examine each pair of consecutive digits.
Check Validity: For each pair:
- Ensure the digits are different.
- Confirm that the frequency of both digits in the string matches their numeric value.
Return Result: If a valid pair is found that satisfies the above conditions, return it as a concatenated string of the two digits. If no valid pair is found throughout the string, the function returns an empty string.

This structured approach efficiently identifies a valid pair by ensuring that we first verify the conditions of the counts, followed by checking each adjacent pair systematically.

Solution Approach

Solution 1: Counting

To solve the problem of finding the first valid pair in the string s, we can employ a straightforward counting technique with the following steps:

Initialize a Count Array: Create an array cnt of length 10 initialized to zeros. This array will be used to keep track of how often each digit (from 0 to 9) appears in the string s.
```
cnt = [0] * 10
```
Count Digit Occurrences: Traverse each character in the string s, convert it to an integer, and increment the corresponding entry in the cnt array. This will help us quickly check if any digit appears exactly as many times as its numeric value.
```
for x in map(int, s):
    cnt[x] += 1
```
Check Adjacent Pairs: Utilize a loop to traverse adjacent pairs of digits. Convert the string into integers and use pairwise to seamlessly access consecutive elements.

Validate Pairs: For each pair (x, y), ensure:

The digits x and y are not the same.
Each digit appears in the string as many times as its value.

If these conditions are satisfied, concatenate the two digits to form a valid pair and return it.

for x, y in pairwise(map(int, s)):
    if x != y and cnt[x] == x and cnt[y] == y:
        return f"{x}{y}"

Return if No Pair Found: If the loop completes without finding a valid pair, return an empty string.
```
return ""
```

By meticulously counting the digits first and checking each adjacency, this approach efficiently returns the first valid pair as required.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution approach using a simplified example. Consider the input string s = "122134".

Initialize a Count Array: Start by setting up an array cnt of length 10, filled with zeros to count digit appearances.
```
cnt = [0] * 10
```
Count Digit Occurrences: Traverse the string s to count each digit's occurrences.
- For '1': Increment cnt[1] to 1.
- For '2': Increment cnt[2] twice, making cnt[2] equal to 2.
- For '3': Increment cnt[3] to 1.
- For '4': Increment cnt[4] to 1.
The count array cnt becomes: [0, 1, 2, 1, 1, 0, 0, 0, 0, 0].
Check Adjacent Pairs: Use a loop to traverse adjacent pairs of digits:
- Pair (1, 2): Different digits, and cnt[1] == 1, cnt[2] == 2 hold true. Thus, this is a valid pair.
Return Result: Since (1, 2) meets the criteria of being a valid pair, concatenate to form "12" and return it.

If no valid pair were found, the function would return an empty string.

By following these steps, the example clearly demonstrates how a valid pair "12" is identified efficiently using counting and pairwise checking.

Solution Implementation

1from itertools import pairwise
2
3class Solution:
4    def findValidPair(self, s: str) -> str:
5        # Initialize a list to count occurrences of each digit from 0 to 9.
6        count = [0] * 10
7      
8        # Count the occurrences of each digit in the string 's'.
9        for digit in map(int, s):
10            count[digit] += 1
11      
12        # Iterate through the string two characters at a time using pairwise.
13        for num1, num2 in pairwise(map(int, s)):
14            # Check if the characters are different and match their count requirement.
15            if num1 != num2 and count[num1] == num1 and count[num2] == num2:
16                # Return the first valid pair as a string.
17                return f"{num1}{num2}"
18      
19        # Return an empty string if no valid pair is found.
20        return ""
21

1class Solution {
2    public String findValidPair(String s) {
3        // Create an array to count the occurrences of each digit (0-9)
4        int[] countArray = new int[10];
5
6        // Fill the countArray with the frequency of each digit in the string
7        for (char character : s.toCharArray()) {
8            countArray[character - '0']++;
9        }
10
11        // Iterate through the string to find a valid pair
12        for (int i = 1; i < s.length(); i++) {
13            // Get the current and previous digits
14            int previousDigit = s.charAt(i - 1) - '0';
15            int currentDigit = s.charAt(i) - '0';
16
17            // Check if the digits are different and their counts match their values
18            if (previousDigit != currentDigit && 
19                countArray[previousDigit] == previousDigit && 
20                countArray[currentDigit] == currentDigit) {
21                // Return the substring representing the valid pair
22                return s.substring(i - 1, i + 1);
23            }
24        }
25
26        // Return an empty string if no valid pair is found
27        return "";
28    }
29}
30

1#include <string>
2#include <vector>
3
4class Solution {
5public:
6    // Method to find a valid pair in the string
7    std::string findValidPair(std::string s) {
8        // Initialize an array to count the occurrences of each digit
9        int count[10] = {};
10      
11        // Count occurrences of each digit in the string
12        for (char c : s) {
13            ++count[c - '0'];
14        }
15      
16        // Iterate through the string to find a valid pair
17        for (size_t i = 1; i < s.size(); ++i) {
18            // Get the numeric values of the current and previous characters
19            int firstDigit = s[i - 1] - '0';
20            int secondDigit = s[i] - '0';
21          
22            // Check if the current pair satisfies the condition
23            if (firstDigit != secondDigit && count[firstDigit] == firstDigit && count[secondDigit] == secondDigit) {
24                // Return the valid pair as a substring of length 2
25                return s.substr(i - 1, 2);
26            }
27        }
28      
29        // Return an empty string if no valid pair is found
30        return "";
31    }
32};
33

1// The function takes a string 's' representing digits and finds a valid pair of consecutive digits.
2function findValidPair(s: string): string {
3    // Create an array to count occurrences of each digit (0-9).
4    const cnt: number[] = Array(10).fill(0); 
5
6    // Count occurrences of each digit in the string 's'.
7    for (const char of s) {
8        ++cnt[+char];
9    }
10
11    // Iterate through the string to check pairs of consecutive digits.
12    for (let i = 1; i < s.length; ++i) {
13        // Extract two consecutive digits x and y.
14        const x = +s[i - 1];
15        const y = +s[i];
16
17        // Check if x and y are different and both have counts equal to their values.
18        if (x !== y && cnt[x] === x && cnt[y] === y) {
19            // Return the valid pair as a string.
20            return `${x}${y}`;
21        }
22    }
23
24    // Return an empty string if no valid pair is found.
25    return '';
26}
27

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. The reason for this is that the algorithm performs a single scan over the string s twice: once to count occurrences of each digit (using cnt[x] += 1) and once to check pairs of adjacent digits (x, y).

The space complexity of the code is O(10), which simplifies to O(1) since the size of cnt is fixed and independent of the input size. The cnt array is used to keep track of the counts of each digit from 0 to 9.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know