【Day 43 】2024-05-20 - 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

[rao-qianlin]

思路

使用滑动窗口的方法

代码

class Solution { public int maxVowels(String s, int k) { int sum = 0; int start = 1; int end = k;

    char[] sc = s.toCharArray () ;
    int len = sc.length;
    for (int i = 0 ; i< k  ; i++){
        if (sc[i]=='a' || sc[i]=='e' ||sc[i]=='i' ||sc[i]=='o' ||sc[i]=='u'){
            sum += 1;
        }
    }
    int max = sum;
    while(end <= sc.length-1){
        if (sc[start-1]=='a' || sc[start-1]=='e' ||sc[start-1]=='i' ||sc[start-1]=='o' ||sc[start-1]=='u'){
            sum -= 1;
        }
        if (sc[end]=='a' || sc[end]=='e' ||sc[end]=='i' ||sc[end]=='o' ||sc[end]=='u'){
            sum += 1;
        }
        if(sum > max){
            max = sum;
        }
        start += 1;
        end += 1;
    }

    return max ;

}

}

[Martina001]

时间复杂度On 空间复杂度 O1 class Solution { public int maxVowels(String s, int k) { // 很明显这是一个滑动窗口的题目，练手写一下试试 // 简单一点，直接判断去掉的那个字符是不是元音即可 int maxVowels =0; for(int i =0;i<k;i++){ maxVowels += isVowel(s.charAt(i))?1:0; } int res = maxVowels; for(int i=k;i<s.length();i++){ int isLeftVowel = isVowel(s.charAt(i-k))?1:0; int isRightVowel = isVowel(s.charAt(i))?1:0; maxVowels += isRightVowel - isLeftVowel; res = Math.max(res,maxVowels); } return res;

// HashMap<Character, Integer> window = new HashMap<>(); /int maxVowels = 0; int right = 0,left = 0; int valid = 0; while (right < s.length()) { char ch = s.charAt(right); right++; // window.put(ch, window.getOrDefault(ch, 0) + 1); if(isVowel(ch)){ valid++; } if(right-left>=k){ if(valid>maxVowels){ maxVowels = valid; } if(valid==k){ return k; } char leftChar = s.charAt(left); left++; // window.put(ch, window.getOrDefault(leftChar, 0) - 1); if(isVowel(leftChar)){ valid--; } } } return maxVowels;/ } private boolean isVowel(char ch){ return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'; } }

[xy147]

js代码

var maxVowels = function (s, k) {
    const dict = new Set(["a", "e", "i", "o", "u"]);
    let ret = 0;
    for (let i = 0; i < k; i++) {
      if (dict.has(s[i])) ret++;
    }

    let temp = ret;
    for (let i = k, j = 0; i < s.length; i++, j++) {
      if (dict.has(s[i])) temp++;
      if (dict.has(s[j])) temp--;

      ret = Math.max(temp, ret);
    }

    return ret;
  };

复杂度分析

时间复杂度：O(n) 空间复杂度：O(1)

[luzhaofeng]

Solution:
    def maxVowels(self, s: str, k: int) -> int:
        n = len(s)
        ans = 0
        for i in range(k):
            if s[i] in "aeiou":
                ans += 1

        cnt = ans
        for i in range(k, n):
            if s[i] in "aeiou":
                cnt += 1
            if s[i - k] in "aeiou":
                cnt -= 1
            ans = max(ans, cnt)
        return ans

[wwz223]

var maxVowels = function(s, k) {
    // arr1 = s.split("")
    let arr2 = 'aeiou'.split("")
    let count = 0 
    let resArr = []

    // 先计数前k位的元音字母的个数
    for(let i = 0; i < k; i++) {
        if(arr2.includes(s[i])){
            count++
        }
    }

    // 再计数前k位后面的元音字母的个数
    let maxCount = count
    for(let i = k; i < s.length; i++) {
        if(arr2.includes(s[i])){
            count++
        }
        // 判断滑过的那位是不是元音
        if(arr2.includes(s[i-k])){
            count--
        }
        maxCount = Math.max(maxCount, count)
    }
    return maxCount
};

[CathyShang]

固定滑动窗口：

• 添加1元素若是元音，则+1

• 删除1元素若是元音，则-1

  class Solution {
  public:
  bool isYuan(char cur){
      if(cur == 'a' ||cur == 'e' ||cur == 'i' ||cur == 'o' ||cur == 'u')
          return true;
      return false;
  }
  int maxVowels(string s, int k) {
      int ans = 0;
      int temp = 0;
  
      for(int l = 0; l < s.size()-k+1; l++){            
          if(l==0){
              for(auto& a:s.substr(l,k)){
                  if(isYuan(a)){
                      temp++;
                  }
              }
          }
          else{
              if(isYuan(s[l-1])){temp--;}
              if(isYuan(s[l+k-1])){temp++;}
          }
          ans = max(ans, temp);
          if(temp==k) break;
      }
      return ans;
  }
  };

• Time O(N)
• Space O(1)

[hillsonziqiu]

思路

滑动窗口

代码

const isVowel = (ch) => {
    return ['a', 'e', 'i', 'o', 'u'].includes(ch) ? 1 : 0;
}
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function(s, k) {
    const len = s.length;
    let count = 0;
    for (let i = 0; i < k; i++) {
        count += isVowel(s[i]);
    }

    let ans = count;
    for (let i = k; i < len; i++) {
        count += isVowel(s[i]) - isVowel(s[i - k]);
        ans = Math.max(ans, count);
    }

    return ans;
};

复杂度分析

时间复杂度: O(n)l; 空间复杂度: O(1);

[Dtjk]

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';
    }
}