What is the easiest approach to solve DI String Match?

Use a two-pointer scanning method: assign the smallest remaining number for 'I' and the largest for 'D', ensuring the pattern holds.

Can multiple valid permutations exist for the same DI string?

Yes, different sequences of number assignments can satisfy the 'I' and 'D' conditions, but any single valid permutation is acceptable.

What is the time complexity of the two-pointer solution?

The algorithm runs in O(N) time, processing each character of the string once, with O(1) additional space for pointers.

How do I handle large input sizes efficiently?

Maintain just the low and high pointers without extra data structures; this ensures linear time and minimal space usage.

Why is the pattern called 'Two-pointer scanning with invariant tracking'?

Because it scans the string with two pointers representing the smallest and largest available numbers, maintaining the invariant that all assigned numbers satisfy the 'I' and 'D' rules.

#942

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

增减字符串匹配

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中: 如果 perm[i] ，那么 s[i] == 'I' 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D' 给定一个字符串 s ，重构排列 perm 并返回它。…

数组双指针字符串贪心

题目描述

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'

给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。

示例 1：

输入：s = "IDID"
输出：[0,4,1,3,2]

示例 2：

输入：s = "III"
输出：[0,1,2,3]

示例 3：

输入：s = "DDI"
输出：[3,2,0,1]

提示：

1 <= s.length <= 10⁵
s 只包含字符 "I" 或 "D"

lightbulb

解题思路

方法一：贪心

我们可以使用两个指针 low 和 high 分别表示当前的最小值和最大值，然后遍历字符串 s，如果当前字符是 I，那么我们就将 low 加入到结果数组中，并且 low 自增 1；如果当前字符是 D，那么我们就将 high 加入到结果数组中，并且 high 自减 1。

最后，我们将 low 加入到结果数组中，返回结果数组即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 s 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        low, high = 0, len(s)
        ans = []
        for c in s:
            if c == "I":
                ans.append(low)
                low += 1
            else:
                ans.append(high)
                high -= 1
        ans.append(low)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(N) because each character is processed once in a single pass. Space complexity is O(1) beyond the output array, as only two pointers are maintained.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to off-by-one errors when assigning low and high pointers.
question_mark
Clarify that multiple valid permutations exist and returning any is acceptable.
question_mark
Explain how the two-pointer invariant guarantees all 'I' and 'D' constraints are satisfied.

warning

常见陷阱

外企场景

error
Swapping low and high pointers incorrectly leading to invalid permutations.
error
Failing to handle the final element after the loop, leaving it unassigned.
error
Misinterpreting 'I' and 'D' conditions, producing reversed relationships.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return all valid permutations instead of any single one.
arrow_right_alt
Handle strings with additional characters representing equality or custom ordering.
arrow_right_alt
Solve in-place if the input array representation is given instead of a string.

help

常见问题

外企场景

继续练习

#948 令牌放置 #969 煎饼排序 #881 救生艇