力扣每日一题 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)