Katkat
Back

Validate whether a binary string is good

VoleonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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

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