Question

1839. Longest Substring Of All Vowels in Order

中文文档

Description

A string is considered beautiful if it satisfies the following conditions:

• Each of the 5 English vowels ('a', 'e', 'i', 'o', 'u') must appear at least once in it.
• The letters must be sorted in alphabetical order (i.e. all 'a's before 'e's, all 'e's before 'i's, etc.).

For example, strings "aeiou" and "aaaaaaeiiiioou" are considered beautiful, but "uaeio", "aeoiu", and "aaaeeeooo" are not beautiful.

Given a string word consisting of English vowels, return _the length of the longest beautiful substring of _word_. If no such substring exists, return _0.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
Output: 13
Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.

Example 2:

Input: word = "aeeeiiiioooauuuaeiou"
Output: 5
Explanation: The longest beautiful substring in word is "aeiou" of length 5.

Example 3:

Input: word = "a"
Output: 0
Explanation: There is no beautiful substring, so return 0.

 

Constraints:

• 1 <= word.length <= 5 * 105
• word consists of characters 'a', 'e', 'i', 'o', and 'u'.

Solutions

Solution 1: Two Pointers + Simulation

We can first transform the string word. For example, for word="aaaeiouu", we can transform it into data items ('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2) and store them in an array arr. Each data item's first element represents a vowel, and the second element represents the number of times the vowel appears consecutively. This transformation can be implemented using two pointers.

Next, we traverse the array arr, each time taking $5$ adjacent data items, and judge whether the vowels in these data items are 'a', 'e', 'i', 'o', 'u' respectively. If so, calculate the total number of times the vowels appear in these $5$ data items, which is the length of the current beautiful substring, and update the maximum value of the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string word.

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

class Solution {
  public int longestBeautifulSubstring(String word) {
    int n = word.length();
    List<Node> arr = new ArrayList<>();
    for (int i = 0; i < n;) {
      int j = i;
      while (j < n && word.charAt(j) == word.charAt(i)) {
        ++j;
      }
      arr.add(new Node(word.charAt(i), j - i));
      i = j;
    }
    int ans = 0;
    for (int i = 0; i < arr.size() - 4; ++i) {
      Node a = arr.get(i), b = arr.get(i + 1), c = arr.get(i + 2), d = arr.get(i + 3),
         e = arr.get(i + 4);
      if (a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u') {
        ans = Math.max(ans, a.v + b.v + c.v + d.v + e.v);
      }
    }
    return ans;
  }
}

class Node {
  char c;
  int v;

  Node(char c, int v) {
    this.c = c;
    this.v = v;
  }
}

class Solution {
public:
  int longestBeautifulSubstring(string word) {
    vector<pair<char, int>> arr;
    int n = word.size();
    for (int i = 0; i < n;) {
      int j = i;
      while (j < n && word[j] == word[i]) ++j;
      arr.push_back({word[i], j - i});
      i = j;
    }
    int ans = 0;
    for (int i = 0; i < (int) arr.size() - 4; ++i) {
      auto& [a, v1] = arr[i];
      auto& [b, v2] = arr[i + 1];
      auto& [c, v3] = arr[i + 2];
      auto& [d, v4] = arr[i + 3];
      auto& [e, v5] = arr[i + 4];
      if (a == 'a' && b == 'e' && c == 'i' && d == 'o' && e == 'u') {
        ans = max(ans, v1 + v2 + v3 + v4 + v5);
      }
    }
    return ans;
  }
};

func longestBeautifulSubstring(word string) (ans int) {
  arr := []pair{}
  n := len(word)
  for i := 0; i < n; {
    j := i
    for j < n && word[j] == word[i] {
      j++
    }
    arr = append(arr, pair{word[i], j - i})
    i = j
  }
  for i := 0; i < len(arr)-4; i++ {
    a, b, c, d, e := arr[i], arr[i+1], arr[i+2], arr[i+3], arr[i+4]
    if a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u' {
      ans = max(ans, a.v+b.v+c.v+d.v+e.v)
    }
  }
  return
}

type pair struct {
  c byte
  v int
}