当前位置: 首页 > article >正文

【Leetcode 每日一题】3306. 元音辅音字符串计数 I

问题背景

给你一个字符串 w o r d word word 和一个 非负 整数 k k k
返回 w o r d word word子字符串 中,每个元音字母(‘a’、‘e’、‘i’、‘o’、‘u’)至少 出现一次,并且 恰好 包含 k k k 个辅音字母的子字符串的总数。

数据约束

  • 5 ≤ w o r d . l e n g t h ≤ 250 5 \le word.length \le 250 5word.length250
  • w o r d word word 仅由小写英文字母组成。
  • 0 ≤ k ≤ w o r d . l e n g t h − 5 0 \le k \le word.length - 5 0kword.length5

解题过程

出现次数相关的问题,首先想到要用哈希表来统计频次。
进一步来看,这题如果将所求问题转化为 至少包含 k k k 个辅音字母,会方便很多,那么恰好可以表示为至少 k k k 个和至少 ( k + 1 ) (k + 1) (k+1) 个之差。

具体实现

class Solution {
    private String VOWEL = "aeiou";

    public int countOfSubstrings(String word, int k) {
        char[] chW = word.toCharArray();
        return cal(chW, k) - cal(chW, k + 1);
    }

    private int cal(char[] chW, int k) {
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        int count = 0;
        for (int left = 0, right = 0; right < chW.length; right++) {
            char inChar = chW[right];
            if (VOWEL.indexOf(inChar) >= 0) {
                map.merge(inChar, 1, Integer::sum);
            } else {
                count++;
            }
            while (map.size() == 5 && count >= k) {
                char outChar = chW[left];
                if (VOWEL.indexOf(outChar) >= 0) {
                    if (map.merge(outChar, -1, Integer::sum) == 0) {
                        map.remove(outChar);
                    }
                } else {
                    count--;
                }
                left++;
            }
            res += left;
        }
        return res;
    }
}

http://www.kler.cn/a/588961.html

相关文章:

  • linux:环境变量,进程地址空间
  • 网络编程基础
  • 算法日记41:思维提升(最大gcd+好数组+简单的减法+球的颜色)
  • Cookie与Session详解
  • QuickAPI 和 DBAPI 谁更香?SQL生成API工具的硬核对比(一)
  • 从零实现区块链共识算法:用Python解锁去中心化世界的关键
  • 企业管理杂谈:产品经理的选拔和培养——企业产品创新发展的关键
  • Python核心语法-数据基本运算(一)
  • 玩转python:通俗易懂掌握高级数据结构:collections模块之defaultdict
  • Android第二次面试总结(项目拷打实战)
  • 线性代数(1)用 excel 计算鸡兔同笼
  • 0CTF 2016 piapiapia 1
  • Kafka的流量控制机制
  • 玩转python:通俗易懂掌握高级数据结构-collections模块之UserList
  • AI大语言模型LLM学习-基于Vue3的AI问答页面
  • 深入解析前后端分离架构:原理、实践与最佳方案
  • [IP]RGMII
  • 通过deepseek学习lua写网页
  • 人工智能与机器学习——系统学习规划
  • 鸿蒙应用开发—ZDbUtil高效使用数据库