3438. Find Valid Pair of Adjacent Digits in String

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.

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

Solutions

Solution 1: Counting

Thinking

A valid pair uses two distinct digits whose global frequencies equal the digits themselves. \(|s|\le 100\), so a count plus one adjacent scan is enough.

Counting while scanning would miss occurrences to the right of the pair.

We fill a length-\(10\) frequency array first, then return the leftmost adjacent pair with \(x\neq y\), \(cnt[x]=x\) and \(cnt[y]=y\).

We can use an array \(\textit{cnt}\) of length \(10\) to record the occurrences of each digit in the string \(\textit{s}\).

Then, we traverse the adjacent digit pairs in the string \(\textit{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 \(\textit{s}\). The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the character set of the string \(\textit{s}\). In this problem, \(\Sigma = \{1, 2, \ldots, 9\}\).

Python3JavaC++GoTypeScript

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

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

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

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

3438. Find Valid Pair of Adjacent Digits in String

Description

Solutions

Solution 1: Counting

Comments