Validate whether a binary string is good
Company: Voleon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a binary string `s` consisting only of characters `'0'` and `'1'`.
Define a **good string** recursively by the grammar:
- `'0'` is a good string.
- If `a` and `b` are good strings, then `'1' + a + b` (concatenation) is also a good string.
Examples of good strings:
- `"0"`
- `"100"` (=`1` + `0` + `0`)
- `"11000"` (=`1` + `100` + `0`)
- `"1100100"` (=`1` + `100` + `100`)
### Task
Return whether `s` is a good string.
### Requirements
- Target time complexity: **O(n)**
- Use **O(1)** or **O(n)** extra space.
### Input/Output
- Input: string `s`
- Output: boolean (`true` if good, else `false`)
### Constraints (reasonable interview constraints)
- `1 <= len(s) <= 10^6`
Overview: This question evaluates understanding of recursive grammars and string parsing, focusing on designing linear-time algorithms and managing space constraints for validity checks on binary strings.
Read the full Voleon Software Engineer interview experience this question came from
You are given a binary string s consisting only of characters '0' and '1'. A string is called good if it can be generated by the following recursive grammar: '0' is good; if a and b are good strings, then '1' + a + b is also good. Return True if s is a good string, otherwise return False.
Constraints
- 1 <= len(s) <= 10^6
- s[i] is either '0' or '1'
- Target time complexity: O(n)
- Extra space: O(1) or O(n)
Examples
Input: ('0',)
Expected Output: True
Explanation: The single string '0' is directly defined as good.
Input: ('1',)
Expected Output: False
Explanation: A '1' must be followed by two good strings, but none are present.
Hints
- Think of '1' as an internal node that must have two child good strings, and '0' as a leaf.
- Track how many unresolved child positions are currently required while scanning from left to right.