<p>You are given a positive integer <code>n</code>.</p>

<p>A binary string <code>x</code> is <strong>valid</strong> if all <span data-keyword="substring-nonempty">substrings</span> of <code>x</code> of length 2 contain <strong>at least</strong> one <code>&quot;1&quot;</code>.</p>

<p>Return all <strong>valid</strong> strings with length <code>n</code><strong>, </strong>in <em>any</em> order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 3</span></p>

<p><strong>Output:</strong> <span class="example-io">[&quot;010&quot;,&quot;011&quot;,&quot;101&quot;,&quot;110&quot;,&quot;111&quot;]</span></p>

<p><strong>Explanation:</strong></p>

<p>The valid strings of length 3 are: <code>&quot;010&quot;</code>, <code>&quot;011&quot;</code>, <code>&quot;101&quot;</code>, <code>&quot;110&quot;</code>, and <code>&quot;111&quot;</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">[&quot;0&quot;,&quot;1&quot;]</span></p>

<p><strong>Explanation:</strong></p>

<p>The valid strings of length 1 are: <code>&quot;0&quot;</code> and <code>&quot;1&quot;</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 18</code></li>
</ul>

class Solution:
    def validStrings(self, n: int) -> list[str]:
        """
        Generates all valid binary strings of length n.

        Args:
            n: The length of the binary string.

        Returns:
            A list of all valid binary strings of length n.
        """

        result = []
        def backtrack(current_string: str, index: int):
            if index == n:
                result.append(current_string)
                return

            # Try placing '0' and '1' at the current position
            for digit in ['0', '1']:
                # Check if placing '0' is valid (at least one '1' in the last two digits)
                if index >= 1 and current_string[-1] == '0' and digit == '0':
                    continue

                # If valid, recursively call backtrack
                backtrack(current_string + digit, index + 1)

        # Start with an empty string
        backtrack("", 0)
        return result

def _driver():
    n1 = 3
    solution = Solution()
    print(solution.validStrings(n1))  # Output: ['010', '011', '101', '110', '111']

    n2 = 1
    solution = Solution()
    print(solution.validStrings(n2))  # Output: ['0', '1']

_driver() 

37