力扣每日一题 3258. 统计满足 K 约束的子字符串数量 I

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。

返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。

如果数据范围大的话，这题目还真有点难度。但是它的数据太小了，直接暴力就行，只能算简单中的简单了。思路没啥可说的，就按题目要求的做，找到所有的子串，然后检查是否满足0和1的数量最多为k

class Solution {
public:vector<string> enumerate(string s){vector<string> ret;int d=1, len=s.length();while (d<=len){for (int i=0; i<=len-d; ++i){ret.push_back(s.substr(i, d));cout << s.substr(i, d) << endl;}++d;}return ret;}bool k_strain(string s, int k){int num0=0, num1=0;for (char i:s){if (i&1) ++num1;else ++num0;}return num0<=k || num1<=k;}int countKConstraintSubstrings(string s, int k) {vector<string> vec = enumerate(s);printf("%d\n", vec.size());int ans = 0;for (auto i:vec){if (k_strain(i, k)) ++ans;}return ans;}
};

时间复杂度应该算O(n^3),n表示字符串的长度，空间复杂度应该是O(n*n)