Skip to content

2063. Vowels of All Substrings 👍

Approach 1: 1D DP

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  long long countVowels(string word) {
    // dp[i] := the sum of the number of vowels of word[0..i), ...,
    // word[i - 1..i)
    vector<long> dp(word.length() + 1);

    for (int i = 1; i <= word.length(); ++i) {
      dp[i] = dp[i - 1];
      if (isVowel(word[i - 1]))
        dp[i] += i;
    }

    return accumulate(dp.begin(), dp.end(), 0L);
  }

 private:
  bool isVowel(char c) {
    static constexpr string_view kVowels = "aeiou";
    return kVowels.find(c) != string_view::npos;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public long countVowels(String word) {
    // dp[i] := the sum of the number of vowels of word[0..i), ...,
    // word[i - 1..i)
    long[] dp = new long[word.length() + 1];

    for (int i = 1; i <= word.length(); ++i) {
      dp[i] = dp[i - 1];
      if (isVowel(word.charAt(i - 1)))
        dp[i] += i;
    }

    return Arrays.stream(dp).sum();
  }

  private boolean isVowel(char c) {
    return "aeiou".indexOf(c) != -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def countVowels(self, word: str) -> int:
    # dp[i] := the sum of the number of vowels of word[0..i), ...,
    # word[i - 1..i)
    dp = [0] * (len(word) + 1)

    for i, c in enumerate(word):
      dp[i + 1] = dp[i]
      if c in 'aeiou':
        dp[i + 1] += i + 1

    return sum(dp)

Approach 2: $O(1)$

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  long long countVowels(string word) {
    long ans = 0;

    for (int i = 0; i < word.length(); ++i)
      if (isVowel(word[i]))
        ans += (i + 1) * (word.length() - i);

    return ans;
  }

 private:
  bool isVowel(char c) {
    static constexpr string_view kVowels = "aeiou";
    return kVowels.find(c) != string_view::npos;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public long countVowels(String word) {
    long ans = 0;

    for (int i = 0; i < word.length(); ++i)
      if (isVowel(word.charAt(i)))
        ans += (i + 1) * (long) (word.length() - i);

    return ans;
  }

  private boolean isVowel(char c) {
    return "aeiou".indexOf(c) != -1;
  }
}

1
2
3
4
5
class Solution:
  def countVowels(self, word: str) -> int:
    return sum((i + 1) * (len(word) - i)
               for i, c in enumerate(word)
               if c in 'aeiou')