tags: Weekly Contest

Weekly Contest 411

3258. Count Substrings That Satisfy K-Constraint I (Easy)

限制 :

• 1 <= s.length <= 50
• 1 <= k <= s.length
• s[i] is either '0' or '1'

Solution

• 這一題要做的事情是看有多少子序列是符合 0的數量<k 或 1的數量 < k
• 簡單解的話就是暴力解。

時間複雜度:

$O(N^2)$

空間複雜度:

$O(1)$

程式碼:

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            int max[2] = {};
            for (int j = i; j < s.size(); j++) {
                max[s[j] - '0'] += 1;
                if (max[0] <= k || max[1] <= k)
                    result++;
                else
                    break;
            }
        }
        return result;
    }
};

2 (Medium)

限制 :

• 104

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼:

3(Medium)

限制 :

• 104

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼:

4(Hard)

限制 :

• 104

時間複雜度:

$O()$

空間複雜度:

$O()$

程式碼: