How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a nan difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Voleon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Voleon during technical interviews.

Validate whether a binary string is good

Q: Validate whether a binary string is good

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.

Company: Voleon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: nan

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`

Quick Answer: 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.

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.

Input: ('100',)

Expected Output: True

Explanation: '100' equals '1' + '0' + '0', so it is good.

Input: ('11000',)

Expected Output: True

Explanation: '11000' equals '1' + '100' + '0', and both parts are good.

Input: ('1100100',)

Expected Output: True

Explanation: '1100100' equals '1' + '100' + '100', where both '100' substrings are good.

Input: ('10',)

Expected Output: False

Explanation: The leading '1' creates two required child strings, but only one '0' is available.

Input: ('000',)

Expected Output: False

Explanation: The first '0' already completes a full good string, so the remaining characters cannot be part of the same valid string.

Input: ('1110000',)

Expected Output: True

Explanation: This is a valid skewed structure: each '1' introduces two required children, and the four '0' leaves satisfy them exactly.

Solution

def solution(s):
    slots = 1

    for ch in s:
        slots -= 1
        if slots < 0:
            return False

        if ch == '1':
            slots += 2
        elif ch != '0':
            return False

    return slots == 0

Time complexity: O(n). Space complexity: O(1).

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.

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