Validate whether a binary string is good
Problem Description
You are given a binary string s consisting only of characters '0' and '1'.
A good string is defined recursively by the following grammar:
'0'is a good string.- If
aandbare good strings, then'1' + a + b(concatenation) is also a good string.
Examples of good strings include:
"0""100"(which is1+0+0)"11000"(which is1+100+0)"1100100"(which is1+100+100)
Task
Determine and return whether the given string s is a good string.
Requirements
- Time Complexity: Target O(n)
- Space Complexity: Target O(1) or O(n) extra space.
Input/Output
- Input: A string
s. - Output: A boolean value (
trueifsis a good string,falseotherwise).
Constraints
1 <= len(s) <= 10^6
AI interview prep
Core dilemma
The central engineering conflict is how to efficiently parse and validate a string against a recursive grammar definition, specifically managing the nested dependencies (a '1' requiring two 'good strings') within strict linear time and minimal space constraints.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Validate whether a binary string is good
Problem Description
You are given a binary string s consisting only of characters '0' and '1'.
A good string is defined recursively by the following grammar:
'0'is a good string.- If
aandbare good strings, then'1' + a + b(concatenation) is also a good string.
Examples of good strings include:
"0""100"(which is1+0+0)"11000"(which is1+100+0)"1100100"(which is1+100+100)
Task
Determine and return whether the given string s is a good string.
Requirements
- Time Complexity: Target O(n)
- Space Complexity: Target O(1) or O(n) extra space.
Input/Output
- Input: A string
s. - Output: A boolean value (
trueifsis a good string,falseotherwise).
Constraints
1 <= len(s) <= 10^6