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

leetcode 3085. 成为 K 特殊字符串需要删除的最少字符数 中等

给你一个字符串 word 和一个整数 k

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j  都成立,则认为 word 是 k 特殊字符串

此处,freq(x) 表示字符 x 在 word 中的出现频率,而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

示例 1:

输入:word = "aabcaba", k = 0

输出:3

解释:可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba",此时 freq('a') == freq('b') == 2

示例 2:

输入:word = "dabdcbdcdcd", k = 2

输出:2

解释:可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd",此时 freq('b') == 2freq('c') == 3freq('d') == 4

示例 3:

输入:word = "aaabaaa", k = 2

输出:1

解释:可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此,word 变为 "aaaaaa",此时每个字母的频率都是 6

提示:

  • 1 <= word.length <= 10^5
  • 0 <= k <= 10^5
  • word 仅由小写英文字母组成。

分析:由于 word 仅由小写英文字母组成,可以先用一个长度为 26 的数组,统计每个字符出现的次数。接着枚举所有出现次数不为 0 的字符,将该字符的出现次数作为最少出现次数,所有大于它出现次数的字符将被删除到符合条件,所有小于它出现次数的字符将被完全删除。最后返回最小删除次数即可。

int minimumDeletions(char* word, int k) {int cnt[30]={0};for(int i=0;word[i];++i)cnt[word[i]-'a']++;int sum=0x3fffffff;for(int i=0;i<26;++i){if(cnt[i]){int temp=cnt[i],count=0;for(int j=0;j<26;++j){if(cnt[j]){int b=cnt[j];if(temp>b)count+=b;else if(b>temp+k)count+=b-(temp+k);}}sum=fmin(count,sum);}}return sum;
}

http://www.lqws.cn/news/468451.html

相关文章:

  • 实现自动化资源调度与弹性伸缩
  • AWS RDS/Aurora 开启 Database Insights 高级模式全攻略
  • Android 终端模拟器 termux app
  • C++ 第一阶段项目二:温度转换工具
  • ubuntu24.4 + ros2 jazzy 安装gazebo
  • 冰箱压缩机电机驱动板【IPM部分】
  • 【StarRocks系列】建表优化
  • Kettle数据抽取(五)转换控件
  • 《map和set的使用介绍》
  • C#测试调用ClosedXML根据批注设置excel单元格内容
  • 细节/数学/滑动窗口
  • Nginx+tomcat集群
  • 多头注意力机制中全连接函数
  • 成长笔记——多串口发送与接收
  • 面试题-函数类型的重载是啥意思
  • Qt + C++ 入门2(界面的知识点)
  • 吐槽之前后端合作开发
  • FastAPI框架的10个重要知识点总结
  • Typora文档另存与图片迁移的一种思路
  • VR飞夺泸定桥沉浸式历史再现​
  • [C++] STL数据结构小结
  • Linux - 安装 git(sudo apt-get)
  • WPF Style样式 全局样式资源字典
  • Qt/C++应用:防御性编程完全指南
  • leetcode332.重新安排行程:优先队列与DFS实现欧拉路径的行程规划
  • 【智能体】n8n聊天获取链接后爬虫知乎
  • 108. 将有序数组转换为二叉搜索树
  • Vue.js核心概念与实践指南:从实例绑定到数据代理
  • opencv try-catch
  • BGP路由反射器(RR)实验详解,结尾有详细脚本