3211. Generate Binary Strings Without Adjacent Zeros

You are given a positive integer n.

A binary string x is valid if all

substrings

of x of length 2 contain at least one "1".

Return all valid strings with length n, in any order.

Example 1:

Input: n = 3

Output: ["010","011","101","110","111"]

Explanation:

The valid strings of length 3 are: "010", "011", "101", "110", and "111".

Example 2:

Input: n = 1

Output: ["0","1"]

Explanation:

The valid strings of length 1 are: "0" and "1".

Constraints:

• 1 <= n <= 18

Solution:

class Solution {
    public List<String> validStrings(int n) {
        List<String> result = new ArrayList<String>();
        int index = 0;
        StringBuilder sb = new StringBuilder();
        helper(n, index, sb, result);
        return result;
    }

    private void helper(int n , int index, StringBuilder sb, List<String> result){
        if (index == n){
            result.add(sb.toString());
            return;
        }

        if (sb.length() == 0 || sb.charAt(sb.length() - 1) != '0'){
            sb.append("0");
            helper(n, index + 1, sb, result);
            sb.deleteCharAt(sb.length() - 1);
        }

        sb.append("1");
        helper(n, index + 1, sb, result);
        sb.deleteCharAt(sb.length() - 1);


    }


}