What defines a valid pair in Find Valid Pair of Adjacent Digits in String?

A valid pair consists of two adjacent digits where each digit occurs in the string exactly as many times as its numeric value.

Can zeros appear in the string for this problem?

No, the string only contains digits '1' through '9'. Including '0' would violate the problem constraints.

What is the best approach to solve this problem efficiently?

Use a hash table to count the frequency of each digit and then scan each adjacent pair to find the first valid one.

What should be returned if no valid adjacent pair exists?

Return an empty string if no pair satisfies the frequency condition.

Does the Hash Table plus String pattern always guarantee O(n) performance?

Yes, because counting digits is O(n) and checking adjacent pairs is O(n), giving an overall linear time solution.

#3438

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

找到字符串中合法的相邻数字

给你一个只包含数字的字符串 s 。如果 s 中两个相邻的数字满足以下条件，我们称它们是合法的：前面的数字不等于第二个数字。两个数字在 s 中出现的次数恰好分别等于这个数字本身。请你从左到右遍历字符串 s ，并返回最先找到的合法相邻数字。如果这样的相邻数字不存在，请你返回一个…

哈希表字符串计数

题目描述

给你一个只包含数字的字符串 s 。如果 s 中两个相邻的数字满足以下条件，我们称它们是 合法的 ：

前面的数字 不等于 第二个数字。
两个数字在 s 中出现的次数恰好分别等于这个数字本身。

请你从左到右遍历字符串 s ，并返回最先找到的合法相邻数字。如果这样的相邻数字不存在，请你返回一个空字符串。

示例 1：

输入：s = "2523533"

输出："23"

解释：

数字 '2' 出现 2 次，数字 '3' 出现 3 次。"23" 中每个数字在 s 中出现的次数都恰好分别等于数字本身。所以输出 "23" 。

示例 2：

输入：s = "221"

输出："21"

解释：

数字 '2' 出现 2 次，数字 '1' 出现 1 次。所以输出 "21" 。

示例 3：

输入：s = "22"

输出：""

解释：

没有合法的相邻数字。

提示：

2 <= s.length <= 100
s 只包含 '1' 到 '9' 的数字。

lightbulb

解题思路

方法一：计数

我们可以用一个长度为 $10$ 的数组 $\textit{cnt}$ 记录字符串 $\textit{s}$ 中每个数字出现的次数。

然后我们遍历字符串 $\textit{s}$ 中的相邻数字对，如果这两个数字不相等且满足这两个数字出现的次数分别等于这两个数字本身，我们就找到了一个合法的相邻数字对，返回即可。

遍历结束后，如果没有找到合法的相邻数字对，我们返回一个空字符串。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $\textit{s}$ 的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 为字符串 $\textit{s}$ 中出现的字符集，本题中 $\Sigma = \{1, 2, \ldots, 9\}$ 。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	complexity is O(n) for counting plus O(n) for scanning adjacent pairs, yielding overall O(n). Space complexity is O(1) since the hash table only stores counts for digits '1' through '9'.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate correctly handle counting digit occurrences with a hash table?
question_mark
Does the candidate correctly check every adjacent pair without skipping potential valid pairs?
question_mark
Is the solution efficient in both time and space considering the small fixed digit set?

warning

常见陷阱

外企场景

error
Ignoring that only digits '1' through '9' are valid and counting '0' can lead to errors.
error
Failing to return the first valid pair and instead returning the last or all pairs.
error
Recomputing counts for each pair instead of precomputing frequencies using a hash table.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find all valid adjacent pairs instead of just the first one.
arrow_right_alt
Allow the string to include '0' and adjust the counting condition accordingly.
arrow_right_alt
Find valid triplets of digits where each digit's frequency equals its numeric value.

help

常见问题

外企场景

继续练习

#3442 奇偶频次间的最大差值 I #3443 K 次修改后的最大曼哈顿距离 #3389 使字符频率相等的最少操作次数