Skip to content

4006. Count Valid Prefixes

Description

You are given a binary string s.

A prefix of s is considered valid if its characters can be rearranged to form an alternating string.

Return the number of valid prefixes of s.

A string is considered alternating if no two adjacent characters are equal.

Β 

Example 1:

Input: s = "00101"

Output: 3

Explanation:

The valid prefixes are:

  • "0": It is already an alternating string.
  • "001": It can be rearranged into "010", which is an alternating string.
  • "00101": It can be rearranged into "01010", which is an alternating string.

Thus, the answer is 3.

Example 2:

Input: s = "101"

Output: 3

Explanation:

All prefixes of s = "101" are already alternating strings. Thus, the answer is 3.

Β 

Constraints:

  • 1 <= s.length <= 100
  • s consists only of '0' and '1'.

Solutions

Solution 1: Counting

A string can be rearranged into an alternating string if and only if the counts of '0' and '1' in it differ by at most \(1\).

Therefore, we traverse the string \(s\) and maintain a variable \(t\) equal to the number of '1's minus the number of '0's in the current prefix (increment by one on '1', decrement by one on '0'). If \(|t| \leq 1\), the current prefix is valid, and we add one to the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

Comments