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

Every day a Leetcode

题目来源：1839. 所有元音按顺序排布的最长子字符串

解法1：滑动窗口

要找的是最长美丽子字符串的长度，我们可以用滑动窗口解决。

设窗口内的子字符串为 window，每当 word[right] >= window.back() 时，说明可以按字典序升序排布，我们都可以将 word[right] 添加进 window 的末尾，我们使用一个集合 cnt 存储每次遇到的 word[right]，当 cnt.size() = 5时，说明所有 5 个英文元音字母都至少出现了一次，更新长度：max_len = max(max_len, (int)window.size())。

如果遇到了不按字典序升序排布的情况，我们发现窗口必须全部清空，于是有：window = “”，cnt.clear()，同时要改变窗口的左边界 left = right，立即将 word[left] 加入进窗口和集合，重新开始遍历。

代码：

/*
 * @lc app=leetcode.cn id=1839 lang=cpp
 *
 * [1839] 所有元音按顺序排布的最长子字符串
 */

// @lc code=start

// 滑动窗口

class Solution
{
public:
    int longestBeautifulSubstring(string word)
    {
        // 特判
        if (word.size() < 5)
            return 0;
        int n = word.size();
        string window;
        unordered_set<char> cnt;
        int max_len = 0, left = 0, right = 0;
        while (right < n)
        {
            if (window.empty() || word[right] >= window.back())
            {
                window += word[right];
                cnt.insert(word[right]);
                right++;
                if (cnt.size() == 5)
                    max_len = max(max_len, (int)window.size());
            }
            else
            {
                window = "";
                cnt.clear();
                left = right;
                window += word[left];
                cnt.insert(word[left]);
                right++;
            }
        }
        return max_len;
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是字符串 word 的长度。

空间复杂度：O(n)，其中 n 是字符串 word 的长度。

解法2：一次遍历

由滑动窗口的启发，我们发现只设立几个变量也能达到相同的效果。

代码：

class Solution
{
public:
    int longestBeautifulSubstring(string word)
    {
        // 特判
        if (word.size() < 5)
            return 0;
        int n = word.size();
        int max_len = 0;
        int vowel = 1, cur_len = 1;
        for (int i = 1; i < n; i++)
        {
            if (word[i] >= word[i - 1])
            {
                cur_len++;
                if (word[i] > word[i - 1])
                    vowel++;
            }
            else
            {
                cur_len = 1;
                vowel = 1;
            }
            if (vowel == 5)
                max_len = max(max_len, cur_len);
        }
        return max_len;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是字符串 word 的长度。

空间复杂度：O(1)。