Validate whether a binary string is good

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