4006. 统计有效前缀数目

题目描述

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

如果 s 的某个前缀的字符可以重新排列成一个交替字符串，那么该前缀被认为是有效的。

返回 s 中有效前缀的数量。

二进制 字符串是仅由 '0' 和 '1' 组成的字符串。

字符串的前缀是指从字符串的开头开始并延伸到其内任意点的 子字符串。

子字符串 是字符串中连续且非空的字符序列。

如果一个字符串中没有两个相邻字符相等，那么它被认为是交替的。

示例 1：

输入： s = "00101"

输出： 3

解释：

有效的前缀是：

"0"：它已经是一个交替字符串。
"001"：可以被重新排列成 "010"，这是一个交替字符串。
"00101"：可以被重新排列成 "01010"，这是一个交替字符串。

因此，答案是 3。

示例 2：

输入： s = "101"

输出： 3

解释：

s = "101" 的所有前缀都已经是交替字符串。因此，答案是 3。

提示：

1 <= s.length <= 100
s 仅由 '0' 和 '1' 组成。

解法

方法一：计数

一个字符串能够重新排列成交替字符串，当且仅当其中 '0' 和 '1' 的数量之差不超过 \(1\)。

因此，我们遍历字符串 \(s\)，用一个变量 \(t\) 维护当前前缀中 '1' 的个数减去 '0' 的个数（遇到 '1' 时加一，遇到 '0' 时减一）。如果 \(|t| \leq 1\)，说明当前前缀是有效的，答案加一。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(s\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def countValidPrefixes(self, s: str) -> int:
        ans = t = 0
        for c in s:
            t += 1 if c == '1' else -1
            ans += 1 if abs(t) <= 1 else 0
        return ans

class Solution {
    public int countValidPrefixes(String s) {
        int ans = 0, t = 0;
        for (char c : s.toCharArray()) {
            t += c == '1' ? 1 : -1;
            if (Math.abs(t) <= 1) {
                ans++;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int countValidPrefixes(string s) {
        int ans = 0, t = 0;
        for (char c : s) {
            t += c == '1' ? 1 : -1;
            if (abs(t) <= 1) {
                ans++;
            }
        }
        return ans;
    }
};

func countValidPrefixes(s string) int {
    ans, t := 0, 0
    for _, c := range s {
        if c == '1' {
            t++
        } else {
            t--
        }
        if t >= -1 && t <= 1 {
            ans++
        }
    }
    return ans
}

function countValidPrefixes(s: string): number {
    let ans = 0;
    let t = 0;
    for (const c of s) {
        t += c === '1' ? 1 : -1;
        if (Math.abs(t) <= 1) {
            ans++;
        }
    }
    return ans;
}

4006. 统计有效前缀数目

题目描述

解法

方法一：计数

评论