<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]:
        # n represents the length of substrings
        # strings are binary

        # if n == 1
            # return ["0","1"]
        # else:
            # start a for loop that goes from 1 to whatever all 1's len n substring is in decimal
                # convert each decimal # to bin and then convert to string and add prefix 0's if needed
                # add each entry to a list

        if n == 1:
            return ["0","1"]
        else:
            upper_bound = 0
            binary_list = []
            upper_bound += 2 ** n - 1
            
            for i in range(1, upper_bound+1):
                binary_string = self.decimalToBinaryString(i, n)
                if binary_string:
                    binary_list.append(binary_string)
        return binary_list


    def decimalToBinaryString(self, num: int, length: int) -> str:
        # converts the decimal # to binary and then adds prefix zeros to match length
        binary_string = str("{0:b}".format(num))
        if "00" in binary_string:
            return
        elif length - len(binary_string) > 1:
            return
        for i in range(len(binary_string),length):
            binary_string = "0" + binary_string
        return binary_string

175