跳转至

3234. 统计 1 显著的字符串的数量

题目描述

给你一个二进制字符串 s。

请你统计并返回其中 1 显著 的 子字符串 的数量。

如果字符串中 1 的数量 大于或等于 0 的数量的 平方，则认为该字符串是一个 1 显著 的字符串 。

 

示例 1：

输入：s = "00011"

输出：5

解释：

1 显著的子字符串如下表所示。

i j s[i..j] 0 的数量 1 的数量
3 3 1 0 1
4 4 1 0 1
2 3 01 1 1
3 4 11 0 2
2 4 011 1 2

示例 2：

输入：s = "101101"

输出：16

解释：

1 不显著的子字符串如下表所示。

总共有 21 个子字符串，其中 5 个是 1 不显著字符串，因此有 16 个 1 显著子字符串。

i j s[i..j] 0 的数量 1 的数量
1 1 0 1 0
4 4 0 1 0
1 4 0110 2 2
0 4 10110 2 3
1 5 01101 2 3

 

提示：

  • 1 <= s.length <= 4 * 104
  • s 仅包含字符 '0' 和 '1'。

解法

方法一：预处理 + 枚举

根据题目描述，显著字符串满足 \(\textit{cnt}_1 \geq \textit{cnt}_0^2\)，那么 \(\textit{cnt}_0\) 的最大值不超过 \(\sqrt{n}\)，其中 \(n\) 是字符串的长度。因此我们可以枚举 \(\textit{cnt}_0\) 的值，然后计算满足条件的子字符串数量。

我们首先预处理字符串中每个位置开始的第一个 \(0\) 的位置，存储在数组 \(\textit{nxt}\) 中，其中 \(\textit{nxt}[i]\) 表示从位置 \(i\) 开始的第一个 \(0\) 的位置，如果不存在则为 \(n\)。

接下来，我们遍历字符串的每个位置 \(i\) 作为子字符串的起始位置，初始化 \(\textit{cnt}_0\) 的值为 \(0\) 或 \(1\)（取决于当前位置是否为 \(0\)）。然后我们使用一个指针 \(j\) 从位置 \(i\) 开始，逐步跳转到下一个 \(0\) 的位置，同时更新 \(\textit{cnt}_0\) 的值。

对于从位置 \(i\) 开始，且包含 \(\textit{cnt}_0\) 个 \(0\) 的子字符串，最多可以包含 \(\textit{nxt}[j + 1] - i - \textit{cnt}_0\) 个 \(1\)。如果这个数量大于等于 \(\textit{cnt}_0^2\)，则说明存在满足条件的子字符串。此时需要判断字符串从右端点 \(\textit{nxt}[j + 1] - 1\) 向左移动多少个位置，可以使得子字符串仍然满足条件。具体来说，右端点一共可以有 \(\min(\textit{nxt}[j + 1] - j, \textit{cnt}_1 - \textit{cnt}_0^2 + 1)\) 种选择方式。我们将这些数量累加到答案中。然后将指针 \(j\) 移动到下一个 \(0\) 的位置，继续枚举下一个 \(\textit{cnt}_0\) 的值，直到 \(\textit{cnt}_0^2\) 超过字符串长度为止。

时间复杂度 \(O(n \times \sqrt{n})\)，空间复杂度 \(O(n)\)，其中 \(n\) 是字符串的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        nxt = [n] * (n + 1)
        for i in range(n - 1, -1, -1):
            nxt[i] = nxt[i + 1]
            if s[i] == "0":
                nxt[i] = i
        ans = 0
        for i in range(n):
            cnt0 = int(s[i] == "0")
            j = i
            while j < n and cnt0 * cnt0 <= n:
                cnt1 = (nxt[j + 1] - i) - cnt0
                if cnt1 >= cnt0 * cnt0:
                    ans += min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1)
                j = nxt[j + 1]
                cnt0 += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int numberOfSubstrings(String s) {
        int n = s.length();
        int[] nxt = new int[n + 1];
        nxt[n] = n;
        for (int i = n - 1; i >= 0; --i) {
            nxt[i] = nxt[i + 1];
            if (s.charAt(i) == '0') {
                nxt[i] = i;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int cnt0 = s.charAt(i) == '0' ? 1 : 0;
            int j = i;
            while (j < n && 1L * cnt0 * cnt0 <= n) {
                int cnt1 = nxt[j + 1] - i - cnt0;
                if (cnt1 >= cnt0 * cnt0) {
                    ans += Math.min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
                }
                j = nxt[j + 1];
                ++cnt0;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        vector<int> nxt(n + 1);
        nxt[n] = n;
        for (int i = n - 1; i >= 0; --i) {
            nxt[i] = nxt[i + 1];
            if (s[i] == '0') {
                nxt[i] = i;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int cnt0 = s[i] == '0' ? 1 : 0;
            int j = i;
            while (j < n && 1LL * cnt0 * cnt0 <= n) {
                int cnt1 = nxt[j + 1] - i - cnt0;
                if (cnt1 >= cnt0 * cnt0) {
                    ans += min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
                }
                j = nxt[j + 1];
                ++cnt0;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func numberOfSubstrings(s string) int {
    n := len(s)
    nxt := make([]int, n+1)
    nxt[n] = n
    for i := n - 1; i >= 0; i-- {
        nxt[i] = nxt[i+1]
        if s[i] == '0' {
            nxt[i] = i
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        cnt0 := 0
        if s[i] == '0' {
            cnt0 = 1
        }
        j := i
        for j < n && int64(cnt0*cnt0) <= int64(n) {
            cnt1 := nxt[j+1] - i - cnt0
            if cnt1 >= cnt0*cnt0 {
                ans += min(nxt[j+1]-j, cnt1-cnt0*cnt0+1)
            }
            j = nxt[j+1]
            cnt0++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function numberOfSubstrings(s: string): number {
    const n = s.length;
    const nxt: number[] = Array(n + 1).fill(0);
    nxt[n] = n;
    for (let i = n - 1; i >= 0; --i) {
        nxt[i] = nxt[i + 1];
        if (s[i] === '0') {
            nxt[i] = i;
        }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        let cnt0 = s[i] === '0' ? 1 : 0;
        let j = i;
        while (j < n && cnt0 * cnt0 <= n) {
            const cnt1 = nxt[j + 1] - i - cnt0;
            if (cnt1 >= cnt0 * cnt0) {
                ans += Math.min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
            }
            j = nxt[j + 1];
            ++cnt0;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
impl Solution {
    pub fn number_of_substrings(s: String) -> i32 {
        let n = s.len();
        let mut nxt = vec![n; n + 1];

        for i in (0..n).rev() {
            nxt[i] = nxt[i + 1];
            if &s[i..i + 1] == "0" {
                nxt[i] = i;
            }
        }

        let mut ans = 0;
        for i in 0..n {
            let mut cnt0 = if &s[i..i + 1] == "0" { 1 } else { 0 };
            let mut j = i;
            while j < n && (cnt0 * cnt0) as i64 <= n as i64 {
                let cnt1 = nxt[j + 1] - i - cnt0;
                if cnt1 >= (cnt0 * cnt0) {
                    ans += std::cmp::min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
                }
                j = nxt[j + 1];
                cnt0 += 1;
            }
        }

        ans as i32
    }
}

评论