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

结果：

复杂度分析：

时间复杂度：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;}
};

结果：

复杂度分析：

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

空间复杂度：O(1)。