azl397985856 commented 2 years ago

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

HuiWang1020 commented 2 years ago

Idea

fixed-size sliding window

calculate the valid letters in range of length k
add the element i and delete the element at index i - k
update the answer

Code

class Solution {
    public int maxVowels(String s, int k) {
        if (s == null || s.length() < k) return 0;
        int match = 0;
        for (int i = 0; i < k; i++) {
            if (check(s.charAt(i))) match++;
        } 
        int max = match;

        for (int i = k; i < s.length(); i++) {
            if (check(s.charAt(i))) match++;
            if (check(s.charAt(i - k))) match--;
            max = Math.max(max, match);
        }
        return max;
     }

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

Complexity

time=o(n) space=o(1)

MichaelXi3 commented 2 years ago

Idea

维护一个固定长度的滑动窗口

Code

class Solution {
public static boolean check(char ch) {
    return (ch == 'a' || ch == 'e' || ch == 'i' | ch == 'o' || ch == 'u');
}
public int maxVowels(String s, int k) {
    int max = 0, n = s.length();
    int count = 0;
    for(int i = 0; i < k; i++) {
        if(check(s.charAt(i))) count++;
    }
    max = count;
    // build first window size k
    for(int  i = k; i < n; i++) {
        // remove the contribution of the (i - k)th character which is no longer in the window
        if(check(s.charAt(i - k))) count--;
        // add the contribution of the current character
        if(check(s.charAt(i))) count++;
        // update max at for each window of size k
        max = Math.max(max, count);
    }
    return max;
}
}

Complexity

Time: O(N)
Space: O(1)

yanjyumoso commented 2 years ago

Window Sliding

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

        ans = 0
        cur = 0

        vowels = "aeiou"

        for i in range(k):
            if s[i] in vowels:
                cur += 1
        ans = cur

        l, r = 0, k

        while r < len(s):

            if s[l] in vowels:
                cur -= 1
            if s[r] in vowels:
                cur += 1
            ans = max(ans, cur)

            l += 1
            r += 1

        return ans

Time: O(N)
Space: O(1)

gitbingsun commented 2 years ago

题目地址(1456. 定长子串中元音的最大数目)

https://leetcode.cn/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

前置知识

关键点

Sliding window

代码

语言支持：C++

C++ Code:


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

    int maxVowels(string s, int k) {
        int ret = 0;
        int localMax = 0;
        for (int i = 0; i < k; i++) {
            if (isVow(s.at(i))) {
                localMax++;
            }
        }       
        ret = max(ret, localMax);

        for (int i = k; i < s.length(); i++) {
            if (i-k>=0 && isVow(s.at(i-k))) {
                localMax--;
            }
            if (isVow(s.at(i))) {
                localMax++;
            }
            ret = max(ret, localMax);
        }

        return ret;
    }
};

复杂度分析

令 n 为数组长度。

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

maybetoffee commented 2 years ago

class Solution {
    public int maxVowels(String s, int k) {
        int len = s.length();
        int sub = 0;
        for(int i = 0; i <  k; i++){
            sub += isVowel(s.charAt(i));
        }
        int res = sub;
        for(int i = k; i < len; i++){
            sub  = sub + isVowel(s.charAt(i)) - isVowel(s.charAt(i-k));
            res = Math.max(res, sub);
        }
        return res;
    }
    public int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }
}

nancychien commented 2 years ago

ideas: sliding window

def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        ans = cnt = 0
        for i, c in enumerate(s):
            if c in vowels:
                cnt += 1
            if i >= k and s[i - k] in vowels:
                cnt -= 1
            ans  = max(cnt, ans)
        return ans

Time: O(n) Space: O(1)

ZacheryCao commented 2 years ago

idea

slifin window

Code

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = 0
        v = set(['a', 'e','i','o','u'])
        i, j = 0, 0
        cur = 0
        for _ in range(k):
            if s[j] in v:
                cur += 1
            j += 1
        ans = max(ans, cur)
        while j<len(s):
            if s[i] in v:
                cur -=1
            if s[j] in v:
                cur += 1
            i += 1
            j += 1
            ans = max(ans, cur)
        return ans

freedom0123 commented 2 years ago

class Solution {
    public int isVowel(char c) {
        if(c == 'a') return 1;
        if(c == 'e') return 1;
        if(c == 'i') return 1;
        if(c == 'o') return 1;
        if(c == 'u') return 1;
        return 0;
    }
    public int maxVowels(String s, int k) {
        int n = s.length();
        int ans = 0;//用于记录全局答案
        for(int i = 0; i < k && i < n; i++) {
            if(isVowel(s.charAt(i)) == 1) ans++;
        }
        System.out.println(ans);
        int left = 0;
        int tem = ans; // 用于维护一个窗口中的最值
        for(int right = k; right < n; right++) {
            tem = tem + isVowel(s.charAt(right)) - isVowel(s.charAt(left));
            ans = Math.max(ans,tem);
            left++;
        }
        return ans;  
    }
}

KWDFW commented 2 years ago

Day43

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

javascript #滑动窗口

思路

1、设置一个哈希表记录元音字母

2、建立一个滑动窗口，每次根据窗口的变动调整元音字母的计数

3、找出元音字母计数的最大值

代码

var maxVowels = function(s, k) {
  let res=0,count=0
  //res:结果，count:每k个中的元音字母数
  const obj=new Set(['a','e','i','o','u'])
  //建立一个哈希表来记录字母，方便查找
  for(let j=0;j<k;j++){
    if(obj.has(s[j])) res++ 
  }
  //滑动窗口的初始化
  count=res
  for(let i=0,j=k;j<s.length;i++,j++){
    if(obj.has(s[i])) count--//如果退出的元素是元音就计数减少
    if(obj.has(s[j])) count++//如果增加的元素是元音就计数增加
    res=Math.max(res,count)
  }
  return res
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

ghost commented 2 years ago

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

        vowels = set(['a', 'e', 'i', 'o', 'u'])
        l = r = i = 0
        res = curr = 0

        for letter in s:
            curr += letter in vowels
            if i >= k:
                curr -= s[l] in vowels
                l += 1

            i += 1
            r += 1
            res = max(res, curr)

        return res

zhiyuanpeng commented 2 years ago

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

time O(N) space O(1)

houmk1212 commented 2 years ago

思路

固定窗口的滑动窗口问题

代码

class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length();
        int l = 0;
        int r = k - 1;
        int res = 0;
        int tmp = 0;
        for (int i = l; i < r; i++) {
            if (s.charAt(i) == 'a' || s.charAt(i) == 'e' || s.charAt(i) == 'i' || s.charAt(i) == 'o' || s.charAt(i) == 'u') {
                tmp++;
            }
        }
        while (r < n) {
            if (s.charAt(r) == 'a' || s.charAt(r) == 'e' || s.charAt(r) == 'i' || s.charAt(r) == 'o' || s.charAt(r) == 'u') {
                tmp++;
            }
            res = Math.max(res, tmp);
            if (s.charAt(l) == 'a' || s.charAt(l) == 'e' || s.charAt(l) == 'i' || s.charAt(l) == 'o' || s.charAt(l) == 'u') {
                tmp--;
            }
            l++;
            r++;
        }
        return res;
    }
}

复杂度

时间复杂度：O（n）
空间复杂度：O（1）

ShawYuan97 commented 2 years ago

思路

使用滑动窗口，一次遍历所有元素，记录出现元音字母出现最大次数
关键点

如何移动左边界
如何维护不同窗口之间的元音字母个数

代码

语言支持：Python3

Python3 Code:


class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        """
        1. 找到子串
        2. 元音字母个数最多
        使用滑动窗口维护最大个数信息
        """
        ans = 0
        l = 0
        vowels = {'a','e','i','o','u'}
        curr_nums = 0
        for r in range(len(s)):
            # 遍历字符串 记录当前滑动窗口的元音字母个数
            if s[r] in vowels:
                curr_nums += 1
            # 达到滑动窗口最大长度后，记录到目前为止滑动窗口中具有元音字母最大个数
            if r-l == k-1:
                ans = max(ans,curr_nums)
                # 移动左边界
                if s[l] in vowels:
                    curr_nums -= 1
                l += 1
        return ans

复杂度分析

令 n 为数组长度。

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

caterpillar-0 commented 2 years ago

思路

滑动窗口，需要一个变量来维护固定窗口中的数目

代码

class Solution {
public:
    bool possible(char ch){
        return (ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u');
    }
    int maxVowels(string s, int k) {
        if(s.size()==0){
            return 0;
        }
        int res=0;
        //维护一个滑动窗口
        for(int i=0;i<k;i++){
            if(possible(s[i])){
                res++;
            }
        }
        int tmp=res;//!!!tmp是维护窗口的变量
        for(int left=0,right=k-1;right<s.size()-1;right++,left++){
            if(possible(s[left])){
                tmp--;
            }
            if(possible(s[right+1])){
                tmp++;
            }
            res=max(res,tmp);
        }
        return res;
    }
};

复杂度分析

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

Geek-LX commented 2 years ago

5.13

思路：

滑动窗口

代码：

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        res = 0
        temp = 0
        vowels = set(['a','e','i','o','u'])
        for i in range(k):
            res += s[i] in vowels
        if res==k: return k
        temp = res
        for i in range(k,len(s)):
            temp += (s[i] in vowels) - (s[i-k] in vowels)
            res = max(temp,res)
            if res ==k: return k
        return res

复杂度：

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

1973719588 commented 2 years ago

定窗口会超过时间限制，滑动窗口，一个一个计算这样肯定不会超过时间限制

class Solution(object):
    def maxVowels(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        yuan = ['a','e','i','o','u']
        ans = 0
        l = len(s)

        st = s[0:k]
        aa = 0
        for x in st:
            if x in yuan:
                aa += 1

        ans = max(ans,aa)

        for i in range(l - k):
            # st = s[i:i+k]
            if s[i] in yuan:
                aa -= 1
            if s[i+k] in yuan:
                aa += 1

            ans = max(ans,aa)

        return ans

时间复杂度：O(N) 空间复杂度：O(M)

zjsuper commented 2 years ago

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

carterrr commented 2 years ago

char[] sc = s.toCharArray(); int len = sc.length, r = 0, win = 0, max = 0; if(k > len) k = len; while(r < k) { if(isVowel(sc[r++])) { win++; } } max = win; // 如果开始的时候k > len 这里就会有r = k = len 不会进入while while(r < len) { if(isVowel(sc[r - k])) { win--; } if(isVowel(sc[r++])) { win ++; } max = Math.max(max, win); } return max;

Ellie-Wu05 commented 2 years ago

滑动窗口

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        best = 0
        count = 0

        for i, x in enumerate(s):
            if x in 'aeiou':
                count+=1

            if i>=k and s[i-k] in 'aeiou':

                count-=1

            best = max(best,count)

        return best

复杂度

时间 On

空间 O1

xingchen77 commented 2 years ago

思路

滑动窗口，头进，尾出

代码

    def maxVowels(self, s: str, k: int) -> int:
        res = 0
        temp = 0
        vowels = set(['a','e','i','o','u'])
        for i in range(k):
            res += s[i] in vowels
        if res == k:
            return res 

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

复杂度

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

currybeefer commented 2 years ago

滑动窗口算法，比较常规

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;

VictorHuang99 commented 2 years ago

思路：窗口每次移动时，其中包含的元素只有两个变化：窗口左侧丢弃了一个元素，窗口右侧新增了一个元素在滑动开始时记录一下窗口中的元音个数 count，之后移动窗口时,判断左侧丢弃的元素和右侧新增的元素是不是元音，对应地减少或者增加 count

code:

var maxVowels = function (s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u'])
    let count = 0,
        l = 0,
        r = 0
    while (r < k) {
        vowels.has(s[r]) && count++
        r++
    }
    let max = count
    while (r < s.length) {
        vowels.has(s[r]) && count++
        vowels.has(s[l]) && count--
        l++
        r++
        max = Math.max(max, count)
    }
    return max
};

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

Magua-hub commented 2 years ago


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

YuyingLiu2021 commented 2 years ago

滑动窗口
#tc: O(N)
#sc: O(1)

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

        left = 0
        right = k
        while right < len(s):
            if s[left] in volstset:
                cnt -= 1
            left += 1

            if s[right] in volstset:
                cnt += 1    
            right += 1

            maxcnt = max(maxcnt, cnt)              
        return maxcnt

zhishinaigai commented 2 years ago

思路

滑动窗口

代码

class Solution {
public:
    bool isvo(char a){
        return a=='a'||a=='e'||a=='i'||a=='o'||a=='u';
    }
    int maxVowels(string s, int k) {
        int len=s.size();
        int count=0;
        for(int i=0;i<k;i++){
            count+=isvo(s[i]);
        }
        int ans=count;
        for(int i=k;i<len;i++){
            count=count+isvo(s[i])-isvo(s[i-k]);
            ans=max(ans,count);
        }
        return ans;
    }
};

JiangWenqi commented 2 years ago

C++

Fixed window

class Solution {
private:
    unordered_set<char> vowels{'a', 'e', 'i', 'o', 'u'};

public:
    int maxVowels(string s, int k) {
        int count = 0, res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (vowels.count(s[i])) count++;
            if (i >= k && vowels.count(s[i - k])) count--;
            res = max(count, res);
        }
        return res;
    }
};

O(n) O(1)

miss1 commented 2 years ago

思路

滑动窗口，固定窗口大小

代码

var maxVowels = function(s, k) {
  let count = 0;
  let start = 0, end = 0;
  let set = new Set(['a', 'e', 'i', 'o', 'u']);
  while (end < k) {
    if (set.has(s[end])) count++;
    end++;
  }
  let res = count;
  while (end < s.length) {
    if (set.has(s[end])) count++;
    if (set.has(s[start])) count--;
    res = Math.max(res, count);
    start++;
    end++;
  }
  return res;
};

复杂度

time: O(n)
space: O(1)

577961141 commented 2 years ago

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

题目链接

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

题目思路

滑动窗口
哈希表

思路：

用哈希表记录'a', 'e', 'i', 'o', 'u'，五个元音字母，方便在滑动窗口的比较

滑动窗口经过以下几步统计元音字母

窗口左端弹出一个字符（删除步）
若删除了元音则计数器-1（更新步）
窗口右端加进来一个字符（添加步）
若添加的字符是元音则计数器+1（更新步）

题目的题解code

PHP解法

<?php

class Solution {

    /**
     * @param String $s
     * @param Integer $k
     * @return Integer
     */
    function maxVowels($s, $k) {
        $dict = ['a', 'e', 'i', 'o', 'u'];
        $ret = 0;
        for ($i = 0; $i < $k; $i++) {
            if (in_array($s[$i], $dict)) {
                $ret++;
            }
        }

        $tmp = $ret;

        for ($i = $k, $j = 0; $i < strlen($s); $j++,$i++) {
            if (in_array($s[$j], $dict)) {
                $tmp--;
            }

            if (in_array($s[$i], $dict)) {
                $tmp++;
            }
            $ret = max($tmp, $ret);
        }

    }
}

go解法：

func maxVowels(s string, k int) int {
    var a []string
    a = []string{"a", "e", "i", "o", "u"}

    var ret int
    ret = 0
    for i := 0; i < k; i++ {
        _, ok := Find(a, string(s[i]))

        if ok {
            ret++
        }
    }

    tmp := ret

    j := 0
    for i := k; i < len(s); i++ {

        _, ok1 := Find(a, string(s[i]))
        _, ok2 := Find(a, string(s[j]))

        if ok1 {
            tmp++
        }

        if ok2 {
            tmp--
        }
        if tmp > ret {
            ret = tmp
        }
        j++
    }

    return ret

}

func Find(slice []string, val string) (int, bool) {
    for i, item := range slice {
        if item == val {
            return i, true
        }
    }
    return -1, false
}

时间和空间复杂度

时间复杂度：O(N)，其中 N 是s的长度。
空间复杂度：O(1),没用到额外空间。

PFyyh commented 2 years ago

代码

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

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

oneline-wsq commented 2 years ago

思路

滑动窗口

代码

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

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

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

Davont commented 2 years ago

var maxVowels = function (s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u'])
    let count = 0,
        l = 0,
        r = 0
    while (r < k) {//初始化大小k的窗口
        vowels.has(s[r]) && count++
        r++
    }
    let max = count
    while (r < s.length) {//不断移动窗口
        vowels.has(s[r]) && count++
        vowels.has(s[l]) && count--
        l++
        r++
        max = Math.max(max, count)//更新最大元音数
    }
    return max
};

mo660 commented 2 years ago

思路

滑动窗口+双指针

代码

class Solution {
public:
    bool isVowels(char s){
        return (s =='a')||(s =='e')||(s =='i')||(s =='o')||(s =='u');
    }
    int maxVowels(string s, int k) {
        int ans = -1;
        int count = 0;
        for (int i = 0;i<k;i++){
            if (isVowels(s[i]))
                count++;
        }
        ans = max(ans,count);
        for (int i = k;i<s.length();i++){
            if (isVowels(s[i])) count++;
            if (isVowels(s[i-k])) count--;
            ans = max(ans,count);
        }
        return ans;
    }
};

rzhao010 commented 2 years ago

class Solution {
    public int maxVowels(String s, int k) {
        if (s.length() < k) {
            return -1;
        }

        Set<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');

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

hyh331 commented 2 years ago

Day43 思路

固定距离滑动窗口。

首先计算第一个窗口中元音字母个数。
滑动窗口"右端"向右移动，窗口内的元音字母=右端刚进来的元音字母-左端出去的元音字母，窗口每向右滑动一下，比较一次窗口内元音字母个数，取最大值

写一个isVowels函数，是元音字母返回1，否则返回0。

class Solution {
public:
int isVowels(char ch){
    // if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u'){
    //     return 1;
    // }else{
    //     return 0;
    // }
    //可用三目运算符
    return ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u'? 1 : 0;
}
int maxVowels(string s, int k) {
    int n=s.size();
    int vowels_count=0;
    //首先计算第一个窗口中元音字母个数
    for(int i=0; i<k; i++){
            vowels_count += isVowels(s[i]);
    }
    int ans=vowels_count;
    //滑动窗口"右端"向右移动
    for(int j= k; j<n; j++){
        //窗口内的元音字母=右端刚进来的元音字母-左端出去的元音字母
        vowels_count += isVowels(s[j])-isVowels(s[j-k]);
        //窗口每向右滑动一下，比较一次窗口内元音字母个数，取最大值
        ans = max(ans, vowels_count);
    }
    return ans;
}
};

复杂度分析

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

revisegoal commented 2 years ago

滑动窗口

窗口大小：k

滑动策略：左减右增

class Solution {
public int maxVowels(String s, int k) {
    Set<Character> set = new HashSet<>();
    set.add('a');
    set.add('e');
    set.add('i');
    set.add('o');
    set.add('u');
    int cnt = 0;
    for (int i = 0; i < k && i < s.length(); i++) {
        if (set.contains(s.charAt(i))) {
            cnt++;
        }
    }
    int res = cnt;
    for (int r = k; r < s.length(); r++) {
        if (set.contains(s.charAt(r - k))) {
            cnt--;
        }
        if (set.contains(s.charAt(r))) {
            cnt++;
        }
        res = Math.max(res, cnt);
    }
    return res;
}
}

time: O(n)
space: O(k)

Joyce94 commented 2 years ago

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        res = 0
        temp = 0
        vowels = set(['a','e','i','o','u'])
        for i in range(k):
            res += s[i] in vowels
        if res==k: return k
        temp = res
        for i in range(k,len(s)):
            temp += (s[i] in vowels) - (s[i-k] in vowels)
            res = max(temp,res)
            if res ==k: return k
        return res

LQyt2012 commented 2 years ago

思路

滑动窗口。当窗口合法时，右指针增加，更新窗口内的信息变量即此时窗口内元音的个数。当窗口不合法时，增加左指针，同时更新窗口的信息变量。

代码

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        left = 0
        right = -1
        count = 0
        max_count = 0
        while right < len(s) - 1:
            right += 1
            if s[right] in "aoieu":
                count += 1
            if right - left == k - 1:
                if count > max_count:
                    max_count = count
                if s[left] in "aoieu":
                    count -= 1
                left += 1
        return max_count

func maxVowels(s string, k int) int {
    left := 0
    right := -1
    count := 0
    maxCount := 0
    for right < len(s) - 1 {
        right++
        if s[right] == 'a' || s[right] == 'o' || s[right] == 'i' || s[right] == 'e' || s[right] == 'u' {
            count++
        }
        if right - left == k-1 {
            if count > maxCount {
                maxCount = count
            }
            if s[left] == 'a' || s[left] == 'o' || s[left] == 'i' || s[left] == 'e' || s[left] == 'u' {
                count--
            }
            left++
        }
    }
    return maxCount
}

复杂度分析

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

zhulin1110 commented 2 years ago

题目地址(1456. 定长子串中元音的最大数目)

https://leetcode.cn/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

前置知识

定长的滑动窗口

代码

语言支持：JavaScript

JavaScript Code:


/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function(s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u'])
    let count = 0;
    let l = 0;
    let r = 0;
    while (r < k) {
        if (vowels.has(s[r])) {
            count++;
        }
        r++;
    }
    let max = count;
    while (r < s.length) {
        if (vowels.has(s[r])) {
            count++;
        }
        if (vowels.has(s[l])) {
            count--;
        }
        l++;
        r++;
        max = Math.max(max, count);
    }
    return max;
};

复杂度分析

令 n 为字符串长度。

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

Quieter2018 commented 2 years ago

思路滑动窗口，需要左指针和右指针，窗口向右滑，滑出元音字符计数减一，滑入元音字符计数加一；

代码

class Solution {
public:
    int maxVowels(string s, int k) {
        int left=0;
        int right= k-1;
        int max_length = 0;
        int cur_length = 0;
        for(int i=0;i<k;i++){
            if(i>=s.size()){
                return cur_length;
            }
            if(s[i]=='a'|| s[i]=='e'|| s[i]=='i'|| s[i]=='o'|| s[i]=='u'){
                cur_length++;
            }
        }
        max_length = cur_length;
        for(int i = 1;i<s.size()-k+1;i++){
            left=i-1;
            right = k+i-1;
            if(s[left]=='a'|| s[left]=='e'|| s[left]=='i'|| s[left]=='o'|| s[left]=='u'){
                    cur_length--;
            }
            if(s[right]=='a'|| s[right]=='e'|| s[right]=='i'|| s[right]=='o'|| s[right]=='u'){
                    cur_length++;
            }
            max_length = max(cur_length,max_length);
        }
        return max_length;

    }
};

复杂度分析 时间复杂度：O(n); 空间复杂度：O(k);

KelvinG-LGTM commented 2 years ago

思路

滑动窗口.

代码

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

        left, right = 0, k 
        while right < len(s): 
            right_val = s[right]
            right += 1
            if right_val in VOWELS: 
                vowels_in_win += 1
            left_val = s[left]
            left += 1
            if left_val in VOWELS: 
                vowels_in_win -= 1
            res = max(res, vowels_in_win)
        return res

复杂度分析

时间复杂度

O(N)

空间复杂度

O(1)

XXjo commented 2 years ago

思路

滑动窗口

代码

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

    let temp = res;
    for(let left = 0; left < s.length - k; left++){
        let right = left + k;
        if(vowelDict.has(s[left])) temp--;
        if(vowelDict.has(s[right])) temp++;
        res = Math.max(res, temp);
    }
    return res;
};

复杂度分析

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

youxucoding commented 2 years ago

5月13日

【day43】

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

难度中等

给你字符串 s 和整数 k 。

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

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

示例 1：

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

思路：

滑动窗口思想，维护一个长度为k的窗口，使窗口在字符串上滑动，计算每一时刻窗口中元音字母的个数，取最大值。

代码实现：

class Solution {
    public int maxVowels(String s, int k) {
        HashMap<Character, Integer> need = new HashMap();
        HashMap<Character, Integer> window = new HashMap();
        need.put('a',1); need.put('e',1); need.put('i',1); need.put('o',1); need.put('u',1);
        int left = 0;
        int right = 0;
        int res = Integer.MIN_VALUE;
        int count = 0;
        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                count++;
            }
            if ((right - left) == k) {
                res = Math.max(res, count);
                char cc = s.charAt(left++);
                if(need.containsKey(cc)) {
                    count--;
                }
            }
            if (res == k) {
                break;
            }
        }
        return res == Integer.MIN_VALUE ? 0 : res;

    }
}

复杂度分析：

时间复杂度：O(N)
空间复杂度：O(N)

zzz607 commented 2 years ago

思路

滑动窗口技巧。除了窗口的二个索引外，再使用二个变量来分别记录当前已得到的最大元素数目和当前窗口内的最大元素数目。

窗口每向右滑到一个位置，若：

右边界是元音字母、而左边界是非元音字母，则当前窗口的元音字母数目加1
右边界不是元音字母、而左边界是元音字母，则当前窗口的元音字母数目减1

将当前窗口内的元音字母数目与之前得的最大值相比，然后重复这个过程即可

代码

func maxVowels(s string, k int) int {
    isVowel := func(s byte) bool {
        switch s {
        case 'a', 'e', 'i', 'o', 'u':
            return true
        default:
            return false
        }
    }

    ret := 0
    cVowel, left, right := 0, 0, 0

    for ; right < k; right++ {
        if isVowel(s[right]) {
            ret++
        }
    }
    cVowel = ret

    for right < len(s) {
        if isVowel(s[right]) && !isVowel(s[left]) {
            cVowel++
        } else if !isVowel(s[right]) && isVowel(s[left]) {
            cVowel--
        }

        if cVowel > ret {
            ret = cVowel
        }

        left++
        right++
    }

    return ret
}

复杂度分析

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

xil324 commented 2 years ago

class Solution(object):
    def maxVowels(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        vowel = 'aeiou'; 
        count = 0; 
        ans = 0; 
        left = right = 0; 
        for right in range(len(s)): 
            if s[right] in vowel:
                count += 1; 
            if right - left + 1 == k:
                ans = max (count, ans); 
                if s[left] in vowel:
                    count -= 1; 
                left += 1; 
        return ans;

time complexity: O(n)

taojin1992 commented 2 years ago

/*
1 <= k <= s.length
1 <= s.length <= 10^5
s consists of lowercase English letters.

# Logic:
fixed window of size k 
a,e,i,o,u
adjust left and right, left starts at 0 ,ending at s.length() - k
check new in and out char, adjust count 

# Complexity:
Time:O(n), n = s.length()

Space: O(1), two pointers

# Tests:
s = "rhythms", k = 4

"abciiidef", 3

*/

class Solution {
    public int maxVowels(String s, int k) {
        int l = 0, r = 0;
        int maxVowelNum = 0, count = 0;
        while (l <= s.length() - k) {
            // increase the right boundary
            while (r < s.length() && r - l + 1 <= k) {
                if (s.charAt(r) == 'a' || s.charAt(r) == 'e' || s.charAt(r) == 'i' || s.charAt(r) == 'o' || s.charAt(r) == 'u') {
                   count++;
                }
                r++;
            }
            // track maxCount
            maxVowelNum = Math.max(maxVowelNum, count);
            // once we reach the size = k, increase the left to decrease the window size by 1
            if (s.charAt(l) == 'a' || s.charAt(l) == 'e' || s.charAt(l) == 'i' || s.charAt(l) == 'o' || s.charAt(l) == 'u') {
                count--;
            }
            l++;
        }
        return maxVowelNum;
    }
}

xiayuhui231 commented 2 years ago

题目

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

思路

滑动窗口

代码

int tmp = 0, res = 0;
        for (int i = 0; i < k; i++) {
            if (foo(s[i])) {
                tmp++;
            }
            if(tmp==k) return k;
        }
        res=max(res,tmp);
        for (int i = k; i < s.size(); i++) {
            if (foo(s[i])) {
                tmp++;
            }
            if (foo(s[i - k])) {
                tmp--;
            }
            res = max(res, tmp);
        }

        return res;
    }
    bool foo(char ch) {
        if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
            return true;
        }
        return false;

flyzenr commented 2 years ago

思路
- 滑动窗口
  - 看到“连续子块”，“连续子数组”，就要想到用滑动窗口来解题
  - 一般代码的思路：
    - 1. l 初始化为 0
    - 1. 初始化 r，使得 r - l + 1 等于窗口大小
    - 1. 同时移动 l 和 r
    - 1. 判断窗口内的连续元素是否满足题目限定的条件
        
        4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
        
        4.2 如果不满足，则继续。

Code - 二分法

-

      class Solution:
          def maxVowels(self, s: str, k: int) -> int:
              # 元音集合
              vowel = {'a', 'e', 'i', 'o', 'u'}
              l = total = 0
              r = k
              #先计算第一个滑动窗口中有几个元音
              for a in s[l:r]:
                  if a in vowel:
                      total += 1
                  #如果元音数等于滑动窗口的大小，直接返回
                  if total == k:
                      return total
                      break
              #设置最多元音数的变量res
              res = total
              #遍历剩下的滑动窗口
              for i in range(k,len(s)):
                  #滑动窗口的左端移除，如果左指针的元素在元音里，减去1
                  if s[i-k] in vowel:
                      total -= 1
                  #滑动窗口的右端加入新的元素，如果新加入的元素在元音里，total+1
                  if s[i] in vowel:
                      total += 1
                      # 判断新窗口的元音数total，和之前的最优解的大小，选择更大的。
                      res = max(res,total)
                  ##如果元音数等于滑动窗口的大小，直接返回
                  if res == k:
                      return k
                      break
              return res

复杂度
- 滑动窗口
  - 时间复杂度: $O(n)$
  - 空间复杂度 $O(1)$

Orangejuz commented 2 years ago

代码

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

AConcert commented 2 years ago

var maxVowels = function (s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u'])
    let count = 0,
        l = 0,
        r = 0
    while (r < k) {
        vowels.has(s[r]) && count++
        r++
    }
    let max = count
    while (r < s.length) {
        vowels.has(s[r]) && count++
        vowels.has(s[l]) && count--
        l++
        r++
        max = Math.max(max, count)
    }
    return max
};

maggiexie00 commented 2 years ago

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

leetcode-pp / 91alg-7-daily-check

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

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

入选理由

题目地址

前置知识

题目描述

Idea

Code

Complexity

Idea

Code

Complexity

题目地址(1456. 定长子串中元音的最大数目)

题目描述

前置知识

关键点

代码

idea

Code

javascript #滑动窗口

思路

代码

复杂度分析

思路

代码

复杂度

思路

关键点

代码

思路

代码

复杂度分析

5.13

滑动窗口

代码

复杂度

思路

代码

复杂度

思路

代码

思路

代码

复杂度

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

题目链接

题目思路

题目的题解code

时间和空间复杂度

代码

思路

代码

复杂度分析

思路

代码

Day43 思路

复杂度分析

滑动窗口

思路

代码

复杂度分析

题目地址(1456. 定长子串中元音的最大数目)

题目描述

前置知识

代码

思路

代码

复杂度分析

时间复杂度

空间复杂度

思路

代码

复杂度分析

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

思路：

代码实现：

复杂度分析：

思路

代码