Medium

题目描述

如果一个字符串满足以下条件，则称为美丽字符串：

  • 字符串中包含所有 5 个英文元音字母（‘a’, ’e’, ‘i’, ‘o’, ‘u’）至少一次
  • 字母必须按字母表顺序排列（即所有 ‘a’ 在 ’e’ 之前，所有 ’e’ 在 ‘i’ 之前，等等）

例如，字符串 “aeiou” 和 “aaaaaaeiiiioou” 是美丽字符串，但 “uaeio”、“aeoiu” 和 “aaaeeeooo” 不是美丽字符串。

给定一个由英文元音字母组成的字符串 word，返回 word 中最长美丽子串的长度。如果不存在这样的子串，返回 0。

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

示例 1：

输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出：13
解释：word 中最长的美丽子串是 "aaaaeiiiiouuu"，长度为 13。

示例 2：

输入：word = "aeeeiiiioooauuuaeiou"
输出：5
解释：word 中最长的美丽子串是 "aeiou"，长度为 5。

示例 3：

输入：word = "a"
输出：0
解释：不存在美丽子串，所以返回 0。

约束条件：

  • 1 <= word.length <= 5 * 10^5
  • word 仅由字符 ‘a’、’e’、‘i’、‘o’、‘u’ 组成

解题思路

这道题目要求找到包含所有元音字母且按字母顺序排列的最长子串。关键在于理解什么是"按字母顺序排列"——这意味着子串必须遵循 a...a e...e i...i o...o u...u 的模式。

解题思路：

可以采用滑动窗口的方法来解决：

  1. 状态追踪：使用一个状态变量来追踪当前遇到的最后一个元音字母。因为必须按顺序，所以只需要知道当前到达了哪个元音。

  2. 窗口扩展策略：

    • 从每个 ‘a’ 开始尝试构建美丽子串
    • 对于当前字符，判断是否能继续扩展窗口
    • 如果当前字符等于状态字符，可以继续
    • 如果当前字符是状态字符的下一个元音，更新状态并继续
    • 否则，当前子串结束

  3. 优化细节：

    • 只有当状态到达 ‘u’ 时，才表示找到了一个完整的美丽子串
    • 当遇到无法继续的字符时，如果该字符是 ‘a’，可以从这里开始新的尝试
    • 使用一次遍历即可完成，时间复杂度为 O(n)

这种方法的核心是状态机的思想，每个状态代表当前已经匹配到的最后一个元音字母。

代码实现

class Solution {
public:
    int longestBeautifulSubstring(string word) {
        int n = word.length();
        int maxLen = 0;
        int i = 0;
        
        while (i < n) {
            if (word[i] != 'a') {
                i++;
                continue;
            }
            
            int start = i;
            char expected = 'a';
            
            while (i < n) {
                if (word[i] < expected || word[i] > 'u') {
                    break;
                }
                
                if (word[i] > expected) {
                    if (word[i] != expected + 1) {
                        break;
                    }
                    expected = word[i];
                }
                
                if (expected == 'u') {
                    maxLen = max(maxLen, i - start + 1);
                }
                
                i++;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        max_len = 0
        i = 0
        n = len(word)
        
        while i < n:
            if word[i] != 'a':
                i += 1
                continue
            
            start = i
            expected = 'a'
            
            while i < n:
                if word[i] < expected or word[i] > 'u':
                    break
                
                if word[i] > expected:
                    if ord(word[i]) != ord(expected) + 1:
                        break
                    expected = word[i]
                
                if expected == 'u':
                    max_len = max(max_len, i - start + 1)
                
                i += 1
        
        return max_len

public class Solution {
    public int LongestBeautifulSubstring(string word) {
        int maxLen = 0;
        int i = 0;
        int n = word.Length;
        
        while (i < n) {
            if (word[i] != 'a') {
                i++;
                continue;
            }
            
            int start = i;
            char expected = 'a';
            
            while (i < n) {
                if (word[i] < expected || word[i] > 'u') {
                    break;
                }
                
                if (word[i] > expected) {
                    if (word[i] != expected + 1) {
                        break;
                    }
                    expected = word[i];
                }
                
                if (expected == 'u') {
                    maxLen = Math.Max(maxLen, i - start + 1);
                }
                
                i++;
            }
        }
        
        return maxLen;
    }
}

/**
 * @param {string} word
 * @return {number}
 */
var longestBeautifulSubstring = function(word) {
    let maxLen = 0;
    let i = 0;
    
    while (i < word.length) {
        if (word[i] !== 'a') {
            i++;
            continue;
        }
        
        let start = i;
        let vowelSet = new Set();
        vowelSet.add('a');
        
        while (i < word.length && word[i] === 'a') {
            i++;
        }
        
        while (i < word.length && word[i] === 'e') {
            vowelSet.add('e');
            i++;
        }
        
        while (i < word.length && word[i] === 'i') {
            vowelSet.add('i');
            i++;
        }
        
        while (i < word.length && word[i] === 'o') {
            vowelSet.add('o');
            i++;
        }
        
        while (i < word.length && word[i] === 'u') {
            vowelSet.add('u');
            i++;
        }
        
        if (vowelSet.size === 5) {
            maxLen = Math.max(maxLen, i - start);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每个字符最多被访问两次
空间复杂度O(1)只使用常量级别的额外空间

相关题目