【Day 43 】2022-12-13 - 1456. 定长子串中元音的最大数目

[azl397985856]

1456. 定长子串中元音的最大数目

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length

前置知识

暂无

题目描述

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。
示例 5：

输入：s = "tryhard", k = 4
输出：1

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length

[Elon-Lau]

class Solution: def maxVowels(self, s: str, k: int) -> int:

帮助函数判断是否为元音字母

    def isVowel(ch):
        return int(ch in "aeiou")

    n = len(s)
    # 计算所有元音字母的数量
    vowel_count = sum(1 for i in range(k) if isVowel(s[i]))
    ans = vowel_count
    # 如果k=s长度，则直接返回原因字母总数量
    for i in range(k, n):
        # i为右指针，下一个要进入滑动窗口的值，i-k为左指针下一个要进入滑动窗口的值
        vowel_count += isVowel(s[i]) - isVowel(s[i - k])
        ans = max(ans, vowel_count)   # 结果是所有滑动窗口的最大值
    return ans

[Ryanbaiyansong]

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        n = len(s)
        vowels = "aeiou"
        j=ans=0
        window = 0
        for i, ch in enumerate(s):
            if ch in vowels:
                window+=1

            while j < n and (i-j+1) > k:
                // # 长度大于k了, 需要缩小窗口
                if s[j] in vowels:
                    window -= 1
                j+=1

            if (i-j+1) == k:
                ans = max(ans, window)

        return ans

滑动窗口, 看数据范围

[testplm]

class Solution(object):
    def maxVowels(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        # 滑动窗口
        yuanyin = ['a', 'e', 'i', 'o', 'u']
        currCount = 0
        maxCount = 0
        for index, v in enumerate(s):
            if index >= k:
                if s[index-k] in yuanyin:
                    currCount -= 1
            if s[index] in yuanyin:
                currCount += 1
            maxCount = max(currCount,maxCount)
        return maxCount

[yin02]

class Solution: def maxVowels(self, s: str, k: int) -> int: n = len(s) vowels = "aeiou" j=ans=0 window = 0 for i, ch in enumerate(s): if ch in vowels: window+=1

        while j < n and (i-j+1) > k:
            // # 长度大于k了, 需要缩小窗口
            if s[j] in vowels:
                window -= 1
            j+=1

        if (i-j+1) == k:
            ans = max(ans, window)

    return ans

[wtdcai]

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        if len(s)<k: return 0
        fl = "aeiou"
        res = 0
        for i in range(k):
            if s[i] in fl:
                res += 1
        out = res
        l = 0
        r = l+k-1
        while r < len(s)-1:
            if s[l] in fl:
                res -= 1
            l += 1
            r = l+k-1
            if s[r] in fl:
                res += 1
            out = max(out,res)
        return out

复杂度分析

O(n)
O(1)

[bookyue]

code

    public int maxVowels(String s, int k) {
        int res = 0;
        int cnt = 0;
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        for (int i = 0; i < s.length(); i++) {
            cnt += vowels.contains(s.charAt(i)) ? 1 : 0;

            if (i >= k) cnt -= vowels.contains(s.charAt(i - k)) ? 1 : 0;

            res = Math.max(res, cnt);
        }

        return res;
    }

[snmyj]

class Solution {
public:
    int maxVowels(string s, int k) {
        int size=s.size();
        int max=0,l=0;
        for(int i=0;i<k;i++){
            if(s[i]=='a'||s[i]=='e'||s[i]=='i'|| s[i]=='o'|| s[i]=='u') l++;

        }
        max=l;

        if(size>=1){
        for(int i=1,j=k;j<size;j++,i++){
            if(s[i-1]=='a'||s[i-1]=='e'||s[i-1]=='i'||s[i-1]=='o'||s[i-1]=='u') l--;

            if(s[j]=='a'||s[j]=='e'||s[j]=='i'||s[j]=='o'||s[j]=='u') l++;
              max=max>l?max:l;
                 }
          }
        return max;
    }
};

[FlipN9]

/**
    Sliding Window:     TC: O(N)    SC: O(1)
*/
class Solution {
    public int maxVowels(String s, int k) {
        int N = s.length();
        int cur = 0;
        for (int i = 0; i < k; ++i) {
            cur += isVowel(s.charAt(i));
        }
        int max = cur;
        for (int i = k; i < N; ++i) {
            cur += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            max = Math.max(max, cur);
        }
        return max;
    }

    public int isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ? 1 : 0;
    }
}

[mayloveless]

思路

滑动窗口，窗口大小为固定的k个字母，先计算第一个窗口内的值，滑动时，进入的值符合则计数+1，出去的值符合则计数-1. 记录每次滑动的最大值

代码

var maxVowels = function(s, k) {
    const chs = new Set(['a', 'e', 'i', 'o', 'u']);

    let count = 0;
    for(let i =0;i<k;i++) {
        if (chs.has(s[i])) {
            count++;
        }
    }

    let max = count;
    for(let i = k;i<s.length;i++) {
        if (chs.has(s[i])) {
            count++;
        }
        if (chs.has(s[i-k])) {
            count--;
        }
        max = Math.max(max, count);
    }

    return max;
};

复杂度

时间O(n) 空间O(1)

[zenwangzy]

class Solution {
public:
    int maxVowels(string s, int k) {
      unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
      int cnt = 0, ans = 0;
      int n = s.size();
      for (int i = 0; i < n; i++) {
        if (i >= k) cnt -= vowels.count(s[i - k]);
        cnt += vowels.count(s[i]);
        ans = max(ans, cnt);
      }
      return ans;
    }
};

T:O(n) S:O(1)

[Elsa-zhang]

''' 给你字符串 s 和整数 k 。
    请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
    英文中的元音字母 为(a, e, i, o, u)
'''
class Solution:
    def maxVowels(self, s: str, k: int):

        vowls = set(['a','e','i','o','u'])
        temp = [v for v in s[:k] if v in vowls]
        ans = len(temp)

        if ans == k:
            return k

        for i in range(1, len(s)-k+1):
            if s[i-1] in vowls:
                temp.remove(s[i-1])
            if s[i+k-1] in vowls:
                temp.append(s[i+k-1])
            ans = max(ans, len(temp))

            if ans == k:
                return k

        return ans

s = "tryhard"
k = 3
solution = Solution()
ans = solution.maxVowels(s, k)
print(ans)

[chenming-cao]

解题思路

滑动窗口。窗口大小固定为k。先检查最开始的k个字符，算出元音字符的数目。然后每次向后移动一位，检查刚出窗口和刚入窗口的两个字符，算出更新的元音数目。每次更新最大值，最后返回结果。

代码

class Solution {
    public int maxVowels(String s, int k) {
        int count = 0;
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                count++;
            }
        }
        int max = count;
        for (int j = 1; j <= s.length() - k; j++) {
            if (isVowel(s.charAt(j - 1))) {
                count--;
            }
            if (isVowel(s.charAt(j + k - 1))) {
                count++;
            }
            max = Math.max(max, count);
        }
        return max;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

复杂度分析

• 时间复杂度：O(n)，n为字符串长度
• 空间复杂度：O(1)

[Alyenor]

function maxVowels(s: string, k: number): number {
    const t =['a', 'e', 'i', 'o',  'u']
    const isVowel=(c:string) => t.indexOf(c) !== -1
    let l=0,r=0,cnt=0
    for(;r<k;r++){
        if(isVowel(s[r])) cnt++
    }
    let max=cnt
    for(;r<s.length;r++){
        if(isVowel(s[l])) cnt--
        if(isVowel(s[r])) cnt++
        max=Math.max(max,cnt)
        l++
    }
    return max
};

[Abby-xu]

思路

sliding window

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        i,c,m,n=0,0,0,len(s)
        for j in range(n):
            if s[j] in 'aeiou':
                c+=1
            if j-i+1==k:
                m=max(m,c)
                if s[i] in 'aeiou':
                    c-=1
                i+=1
        return m

复杂度

O(n)/O(1)

[A-pricity]

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function(s, k) {
  let vowel = 'aeiou', len = s.length, count = 0, max = 0, i = 0;

  for (; i < k; i++) {
    let curr = s.charAt(i);
    if (vowel.indexOf(curr) !== -1) count++;
  }
  max = Math.max(max, count);

  for (; i < len; i++) {
    let curr = s.charAt(i),
        last = s.charAt(i - k);
    if (vowel.indexOf(curr) !== -1) count++;
    if (vowel.indexOf(last) !== -1) count--;
    max = Math.max(count, max);
  }

  return max;
};

[guowei0223]

典型的滑动窗口问题。 窗口 = k。如果大于k则收缩left pointer，在收缩left pointer时注意检查是否元音，如果是，则需要扣除。最后更新result。保持最大result。

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = ["a","e","i","o","u"]
        result = 0
        vowel = 0
        left = 0
        right = 0
        while right < len(s):
            if s[right] in vowels:
                vowel += 1
            if right - left + 1 > k:
                if s[left] in vowels:
                    vowel -= 1
                left += 1
            result = max(result, vowel)
            right += 1
        return result

TC : O(n) SC :O(1)

[zywang0]

class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length();
        int vowel_count = 0;
        for (int i = 0; i < k; ++i) {
            vowel_count += isVowel(s.charAt(i));
        }
        int ans = vowel_count;
        for (int i = k; i < n; ++i) {
            vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            ans = Math.max(ans, vowel_count);
        }
        return ans;
    }

    public int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }
}

[tiandao043]

思路

滑动窗口，双指针维护k区间，记录有几个元音，维护一个最大值

代码

class Solution {
public:
    int maxVowels(string s, int k) {
        int n=s.length();
        int l=0,r=0;
        int cnt=0;
        int ans=0;
        while(r<=n){
            if(r-l<k){
                if(s[r]=='a'||s[r]=='e'||s[r]=='i'||s[r]=='o'||s[r]=='u'){
                    cnt++;
                }
                r++;
            }else if((r-l)==k){
                ans=max(ans,cnt);
                if(s[l]=='a'||s[l]=='e'||s[l]=='i'||s[l]=='o'||s[l]=='u'){
                    cnt--;
                }l++;
            }
        }        
        return ans;
    }
};

O(n) O(1)

[Jetery]

1456. 定长子串中元音的最大数目

思路

滑动窗口

代码 (cpp)

class Solution {
public:
    bool check(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    int maxVowels(string s, int k) {
        queue<char> que;
        int ans = 0, cur = 0;
        for (char c : s) {
            que.push(c);
            if (que.size() > k) {
                char del = que.front();
                que.pop();
                if (check(del)) cur -= 1;
            }
            if (check(c)) cur += 1, ans = max(ans, cur);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(k)

[RestlessBreeze]

class Solution {
public:
    bool isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; 
    }

    int maxVowels(string s, int k) {
        int n = s.size();
        int vowel_count = 0;
        for (int i = 0; i < k; ++i) {
            vowel_count += isVowel(s[i]);
        }
        int ans = vowel_count;
        for (int i = k; i < n; ++i) {
            vowel_count += isVowel(s[i]) - isVowel(s[i - k]);
            ans = max(ans, vowel_count);
        }
        return ans;
    }
};

[xuanaxuan]

思路 新窗口元素和 = 旧窗口元素和 - 左边移除的元素 + 右边进来的元素 代码

var maxVowels = function(s, k) {
  if (s == null || s.length < k)
  return 0;
  const vowels=['a', 'e', 'i', 'o', 'u']
  let res=0;
  for (let l = 0; l < k; l++) {
    res+=vowels.includes(s[l])?1:0 ;
  }
  let max=res;
     for (let l = 0; l < s.length-k; l++) {
      const r=k+l
      vowels.includes(s[l])&&res--; 
      vowels.includes(s[r])&&res++; 
      max=Math.max(max,res )
     }
     return max
};

[AtaraxyAdong]

class Solution {
    public int maxVowels(String s, int k) {

        HashSet<Character> vowelSet = new HashSet<>();
        vowelSet.add('a');
        vowelSet.add('e');
        vowelSet.add('i');
        vowelSet.add('o');
        vowelSet.add('u');
        char[] charArray = s.toCharArray();
        int right, result = 0, temp = 0;

        // 初始化窗口
        for (int i = 0; i < k; i++) {
            if (vowelSet.contains(charArray[i])) {
                temp += 1;
            }
        }
        result = Math.max(temp, result);

        for (right = k; right < charArray.length; right++) {
            if (vowelSet.contains(charArray[right])) temp++;
            if (vowelSet.contains(charArray[right - k])) temp--;
            result = Math.max(temp, result);
        }

        return result;
    }
}

[klspta]

class Solution {
    public int maxVowels(String s, int k) {
        int cnt = 0;
        int left = 0;
        int right = 0;
        while(right < s.length() && right < k){
            cnt += isNeed(s.charAt(right)) ? 1 : 0;
            right++;
        }
        int max = cnt;
        while(right < s.length()){
            cnt -= isNeed(s.charAt(left)) ? 1 : 0;
            cnt += isNeed(s.charAt(right)) ? 1 : 0;
            right++;
            left++;
            max = Math.max(max, cnt);
        }
        return max;
    }

    private boolean isNeed(char c){
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

[chiehw]

基本思路：

• 滑动窗口

大致步骤：

1. 初始化 Windows 的值。
2. 从做往右移动，在移动过程中不断计算 value 并更新 ans。

代码：

class Solution {
public:
    bool isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; 
    }

    int init_window_value(const string &s, int k){
        int count = 0;
        for (int i = 0; i < k; ++i) {
            count += isVowel(s[i]);
        }
        return count;
    }

    int move_windows(const string &s, int value, int left_index, int right_index){
        return value - isVowel(s[left_index]) + isVowel(s[right_index]) ;   
    }

    int maxVowels(string s, int k) {
        int n = s.size();
        int count = init_window_value(s, k);
        int ans = count;
        for (int i = k; i < n; ++i) {
            count = move_windows(s, count, i-k, i);
            ans = max(ans, count);
        }
        return ans;
    }
};

复杂度分析：

• 时间复杂度：O(s)
• 空间复杂度：O(1)

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int maxVowels(String s, int k) {
int count = 0;
        int length = s.length();
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                count++;
            }
        }
        int maxCount = count;
        for (int i = k; i < length; i++) {
            if (isVowel(s.charAt(i - k))) {
                count--;
            }
            if (isVowel(s.charAt(i))) {
                count++;
            }
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }

    public boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

}

[sclihuiming]

func maxVowels(s string, k int) int {
    ans := 0
    l := 0
    r := k
    count := 0
    for i := 0; i < k; i++ {
        elem := s[i]
        if elem == 'a' || elem == 'e' || elem == 'i' || elem == 'o' || elem == 'u' {
            count++
        }
    }
    ans = count

    for r < len(s) {
        leftElem := s[l]
        nextElem := s[r]
        if leftElem == 'a' || leftElem == 'e' || leftElem == 'i' || leftElem == 'o' || leftElem == 'u' {
            count--
        }
        if nextElem == 'a' || nextElem == 'e' || nextElem == 'i' || nextElem == 'o' || nextElem == 'u' {
            count++
        }
        if ans < count {
            ans = count
        }
        if ans == k {
            return ans
        }
        l++
        r++
    }
    return ans
}

[paopaohua]

class Solution {
    public int maxVowels(String s, int k) {
        // hash表存字母
        if(s == null || s.length() < k) return 0;

        int res = 0;
        Set<Character> set = new HashSet<>(){{
            add('a');
            add('e');
            add('i');
            add('o');
            add('u');
            }};
        // 从左往右判断第一个窗口
        for(int i = 0;i< k;i++){
            if(set.contains(s.charAt(i))) res++;
        }

        int cur = res;
        for(int i = 1; i < s.length() -k + 1;i++){
            if(set.contains(s.charAt(i - 1))) cur--;
            if(set.contains(s.charAt(i + k - 1))) cur++;
            res = Math.max(res,cur);
        }
        return res;
    }
}

[Alexno1no2]

滑动窗口，比较滑动前后的边界

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        cnt = 0
        for i in range(k):
            if s[i] in vowels:
                cnt += 1
        res = cnt

        for i in range(k, len(s)):
            if s[i - k] in vowels:
                cnt -= 1
            if s[i] in vowels:
                cnt += 1
                res = max(res, cnt)
        return res

[saitoChen]

思路

使用滑动窗口

代码

var maxVowels = function(s, n) {

    const letters = ['a','e','i','o','u'];
    const map = new Map();

    letters.forEach( val => map.set(val,true));

    let  count = 0;

    for(let i = 0 ;i < n ; i++){
        if(map.has(s[i])){
            count++;
        }
    }

    let max = count;

    for(let i = n  ; i< s.length ; i++){
        if(map.has(s[i])){
            count++
        }
        if(map.has(s[i-n])){
            count--;
        }
        max = Math.max(max,count)
    }
    return max
};

[neado]

public int maxVowels(String s, int k) {

    if (s == null || s.length() < k)
        return 0;

    int res = 0;
    Set<Character> set = new HashSet<>(){{
        add('a');add('e');add('i');add('o');add('u');
    }};

    // init
    for (int i = 0; i < k; i++)
        if (set.contains(s.charAt(i)))
            res++;

    int cur = res;
    for (int i = 1; i < s.length() - k + 1; i++) {

        if (set.contains(s.charAt(i - 1)))
            cur--;
        if (set.contains(s.charAt(i + k - 1)))
            cur++;

        res = Math.max(res, cur);
    }

    return res;
}

[whoam-challenge]

class Solution: def maxVowels(self, s: str, k: int) -> int: def isVowel(ch): return int(ch in "aeiou")

    n = len(s)
    vowel_count = sum(1 for i in range(k) if isVowel(s[i]))
    ans = vowel_count
    for i in range(k, n):
        vowel_count += isVowel(s[i]) - isVowel(s[i - k])
        ans = max(ans, vowel_count)
    return ans