Welcome to Subscribe On Youtube

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

We can use an array $\mathit{\text{cnt}}$ of length $10$ to record the occurrences of each digit in the string $\mathit{\text{s}}$.

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

• Java
• C++
• Python
• Go
• TypeScript

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

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

All Problems

All Solutions