Welcome to Subscribe On Youtube

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

Thinking

A prefix is valid if and only if the absolute difference between the counts of '0' and '1' is at most $1$. Recounting both characters on every prefix would be quadratic.

A single variable $t$ tracks the difference from left to right: increment on '1', decrement on '0'. At each index we test $|t|\le 1$.

The whole count is therefore a linear scan; we need not store a count array for every prefix.

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)$.

  • 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;
    }
};

  • 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


  • 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;
}

All Problems

All Solutions