Leetcode 1456 - Maximum Number of Vowels in a Substring of Given Length

題目

Problem#

給你一個字串 s 和一個正整數 k ，問你 s 的長度 k 的所有子字串中，其中母音的數量最大是多少？

• 測資限制:
  • $1 \le s, k \le 10^5$

想法#

• 直覺：暴力求 s 的子字串並數母音數量 $\mathcal{O}(n^2)$ -> TLE

• Sliding Window

  • 兩個 index 指向頭尾 [a, b]，每次往前推進就看 s[a] 與 s[b] 是不是母音，然後加減即可。

• 時間複雜度: $\mathcal{O}(n)$

• 空間複雜度: $\mathcal{O}(1)$

AC Code#