Skip to main content
Talentd

Count Valid Prefixes - Solution & Explanation

EasyStringCounting6 min read
Practice this problem

Problem Statement

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 binary string is a string consisting only of '0' and '1'.

A prefix of a string is a substring that starts from the beginning of the string and extends to any point within it.

A substring is a contiguous non-empty sequence of characters within a string.

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'.

Approach Overview

Problem Overview: Given an array of integers, count how many prefixes of the array are valid, where a valid prefix meets a specific condition (e.g., sum is positive).

Approach 1: Brute Force (O(n^2))

Check every possible prefix by iterating through the array and validating each prefix from the start up to the current index. This approach uses nested loops, making it inefficient for large arrays. Prefer this only for understanding the problem basics.

Approach 2: Single Pass with Tracking (O(n))

Iterate through the array once, maintaining a running sum or other condition tracker. For each element, update the tracker and check if the current prefix meets the validity condition. This approach leverages array iteration and prefix sum techniques for optimal performance.

Recommended for interviews: The single-pass approach is expected in interviews. It demonstrates efficient problem-solving and understanding of array traversal. Brute force shows foundational knowledge, but optimal solutions are preferred.

Solution

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2)O(1)Small arrays or understanding basics
Single PassO(n)O(1)General case, optimal solution

Video Solution

Leetcode 4006: Count Valid Prefixes | Leetcode Biweekly Contest 188 • AlgorithmsWithJT • 5 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Count Valid Prefixes easy or hard?
Count Valid Prefixes is an easy problem with a 76.6% acceptance rate. The optimal solution requires basic array traversal.
Count Valid Prefixes Python/Java solution
Python and Java solutions involve iterating through the array once, updating a tracker, and counting valid prefixes. Code examples are available on FleetCode.
How to solve Count Valid Prefixes in O(n)?
Use a single pass to iterate through the array while maintaining a running sum or condition tracker. Validate each prefix in constant time per element.
What is the best approach for Count Valid Prefixes?
The single-pass approach with O(n) time and O(1) space is optimal. It efficiently tracks the validity condition during iteration.
Is Count Valid Prefixes asked at Google/Amazon/Meta?
Count Valid Prefixes is a common problem in coding interviews, especially at companies testing array manipulation skills.
What data structure is used in Count Valid Prefixes?
Arrays are the primary data structure. No additional structures are needed for the optimal solution.
What is the time complexity of Count Valid Prefixes?
The optimal solution runs in O(n) time with O(1) space, achieved by a single traversal of the array.

Ready to solve this problem?

Practice Count Valid Prefixes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring