破解php网站后台账号密码,中国有名的网站建设公司,wordpress豆瓣,旅游网站自己怎么做目录 3258.统计满足k约束的子串数量 I
题目描述#xff1a;
实现代码与解析#xff1a;
滑动窗口
原理思路#xff1a; 3258.统计满足k约束的子串数量 I
题目描述#xff1a; 给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件#…目录 3258.统计满足k约束的子串数量 I
题目描述
实现代码与解析
滑动窗口
原理思路 3258.统计满足k约束的子串数量 I
题目描述 给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件则认为该字符串满足 k 约束
字符串中 0 的数量最多为 k。字符串中 1 的数量最多为 k。
返回一个整数表示 s 的所有满足 k 约束 的子字符串的数量。 示例 1
输入s 10101, k 1
输出12
解释
s 的所有子字符串中除了 1010、10101 和 0101 外其余子字符串都满足 k 约束。
示例 2
输入s 1010101, k 2
输出25
解释
s 的所有子字符串中除了长度大于 5 的子字符串外其余子字符串都满足 k 约束。
示例 3
输入s 11111, k 1
输出15
解释
s 的所有子字符串都满足 k 约束。
提示
1 s.length 501 k s.lengths[i] 是 0 或 1。
Related Topics
字符串滑动窗口
实现代码与解析
滑动窗口
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int countKConstraintSubstrings(String s, int k) {int n s.length();int res 0;int l 0;int cnt0 0, cnt1 0;for (int r 0; r n; r) {if (s.charAt(r) 0) {cnt0;}if (s.charAt(r) 1) {cnt1;}while (cnt0 k cnt1 k) {if (s.charAt(l) 0) cnt0--;if (s.charAt(l) 1) cnt1--;l;}res r - l 1;}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)
原理思路 遍历右指针记录0和1的个数求出当前右指针情况下满足条件的最长长度。如果满足条件收缩左指针直到满足条件。
