What is the sliding window technique?

The sliding window technique involves expanding and contracting a window over the input to find the solution, while maintaining an efficient state for the computation.

How do I know if my substring is beautiful?

A substring is beautiful if it contains the vowels 'a', 'e', 'i', 'o', and 'u' in the correct order, without any characters in between or out of order.

How do I optimize my solution for large strings?

By using the sliding window approach, you can reduce the need for repetitive checks and ensure the solution scales linearly with the string length.

What is the expected time complexity for this problem?

The expected time complexity is O(n), where n is the length of the input string, as each character is processed at most once.

Can I modify the approach for a different sequence of characters?

Yes, you can adapt the sliding window technique for different sequences by adjusting the conditions for the order of characters within the window.

#1839

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

所有元音按顺序排布的最长子字符串

当一个字符串满足如下条件时，我们称它是美丽的：所有 5 个英文元音字母（ 'a' ， 'e' ， 'i' ， 'o' ， 'u' ）都必须至少出现一次。这些元音字母的顺序都必须按照字典序升序排布（也就是说所有的 'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推…

字符串滑动窗口

题目描述

当一个字符串满足如下条件时，我们称它是 美丽的 ：

所有 5 个英文元音字母（'a' ，'e' ，'i' ，'o' ，'u'）都必须至少出现一次。
这些元音字母的顺序都必须按照 字典序 升序排布（也就是说所有的 'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推）

比方说，字符串 "aeiou" 和 "aaaaaaeiiiioou" 都是 美丽的 ，但是 "uaeio" ，"aeoiu" 和 "aaaeeeooo" 不是美丽的 。

给你一个只包含英文元音字母的字符串 word ，请你返回 word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串，请返回 0 。

子字符串 是字符串中一个连续的字符序列。

示例 1：

输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出：13
解释：最长子字符串是 "aaaaeiiiiouuu" ，长度为 13 。

示例 2：

输入：word = "aeeeiiiioooauuuaeiou"
输出：5
解释：最长子字符串是 "aeiou" ，长度为 5 。

示例 3：

输入：word = "a"
输出：0
解释：没有美丽子字符串，所以返回 0 。

提示：

1 <= word.length <= 5 * 10⁵
word 只包含字符 'a'，'e'，'i'，'o' 和 'u' 。

lightbulb

解题思路

方法一：双指针 + 模拟

我们可以先将字符串 word 做个转化，比如对于 word="aaaeiouu"，我们可以将其转化为数据项 ('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2)，存放在数组 arr 中。其中每个数据项的第一个元素表示元音字母，第二个元素表示该元音字母连续出现的次数。这部分转化可以通过双指针来实现。

接下来，我们遍历数组 arr，每次取相邻的 $5$ 个数据项，判断这些数据项中的元音字母是否分别为 'a', 'e', 'i', 'o', 'u'，如果是，则计算这 $5$ 个数据项中元音字母的总次数，即为当前的美丽子字符串的长度，更新答案的最大值即可。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        arr = []
        n = len(word)
        i = 0
        while i < n:
            j = i
            while j < n and word[j] == word[i]:
                j += 1
            arr.append((word[i], j - i))
            i = j
        ans = 0
        for i in range(len(arr) - 4):
            a, b, c, d, e = arr[i : i + 5]
            if a[0] + b[0] + c[0] + d[0] + e[0] == "aeiou":
                ans = max(ans, a[1] + b[1] + c[1] + d[1] + e[1])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that efficiently handles the sliding window and state updates.
question_mark
Check for the candidate's ability to handle edge cases, such as strings without all vowels in order.
question_mark
Evaluate the candidate's approach to maintaining a running state to track the expected vowels.

warning

常见陷阱

外企场景

error
Overcomplicating the solution with unnecessary recalculations of vowel positions.
error
Ignoring edge cases such as strings shorter than five characters or without the full set of vowels.
error
Failing to handle the order of vowels correctly, especially when vowels repeat.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the solution to return the actual substring rather than its length.
arrow_right_alt
Consider variations where the string contains additional characters beyond vowels.
arrow_right_alt
Adapt the solution to work with a larger set of characters or more complex vowel sequences.

help

常见问题

外企场景

继续练习

#1871 跳跃游戏 VII #1876 长度为三且各字符不同的子字符串 #1888 使二进制字符串字符交替的最少反转次数