Generate Binary Strings Without Adjacent Zeros

• Initialize an empty list, result, to store the valid strings.
• Iterate through all integers from 0 to 2^n - 1. Each integer represents a unique binary string of length n.
• For each integer, convert it to its n-bit binary string representation. This can be done by checking each bit of the integer.
• Check if the generated binary string contains the forbidden substring "00".
• If the string is valid (does not contain "00"), add it to the result list.
• After checking all 2^n possibilities, return the result list.

The core of this method is to map the integers in the range [0, 2^n - 1] to all possible binary strings of length n. For example, if n=3, the integer 5 (binary 101) maps to the string "101". We can implement this by iterating from i = 0 to (1 << n) - 1. Inside the loop, we build a StringBuilder of length n. We iterate from j = n-1 down to 0 to check the bits of i from most significant to least significant. The expression (i & (1 << j)) != 0 checks if the j-th bit of i is set. If it is, we append '1'; otherwise, we append '0'. Once the n-character string is formed, we use a built-in contains method to check for the "00" substring. If it's not found, the string is added to our list of results.

1class Solution {2    public List<String> validStrings(int n) {3        List<String> result = new ArrayList<>();4        // Total number of binary strings of length n is 2^n5        int limit = 1 << n; 6        for (int i = 0; i < limit; i++) {7            StringBuilder sb = new StringBuilder();8            for (int j = n - 1; j >= 0; j--) {9                // Check if the j-th bit is 1 or 010                if ((i & (1 << j)) != 0) {11                    sb.append('1');12                } else {13                    sb.append('0');14                }15            }16            String currentString = sb.toString();17            // Check for "00" substring18            if (!currentString.contains("00")) {19                result.add(currentString);20            }21        }22        return result;23    }24}

• Define a recursive function, let's call it backtrack, that takes the current string being built (e.g., as a StringBuilder) as a parameter.
• Base Case: If the length of the current string equals n, it's a complete valid string. Add it to the results list and return.
• Recursive Step: Based on the last character of the current string:
  • If the last character is '1', we can append either '0' or '1'. Make a recursive call for each possibility, backtracking after each call.
  • If the last character is '0', we can only append '1'. Make a recursive call and backtrack.
• The process is initiated by making separate calls for initial strings "0" and "1".

This approach uses a recursive depth-first search to explore the space of valid binary strings. We define a helper function, backtrack(current, n, result), which takes the current prefix current (as a StringBuilder), the target length n, and the list of result strings.

The recursion is initiated by making two separate calls for the starting characters: one for "0" and one for "1". This handles the strings of length 1 and seeds the recursion for longer strings.

Inside the backtrack function:

1. Base Case: The recursion stops when current.length() equals n. At this point, we have constructed a complete, valid string, which is added to the result list.
2. Recursive Step: The function checks the last character of the current string to decide the next valid moves:
   • If the last character is '1', we have two choices for the next character: '0' or '1'. The function recursively calls itself for both cases. First, it appends '0', makes the recursive call, and then backtracks by removing the '0'. Then, it does the same for '1'.
   • If the last character is '0', the only valid next character is '1' to avoid a "00" sequence. The function appends '1', makes the recursive call, and then backtracks.

Using a StringBuilder and deleting the last character for backtracking is crucial for efficiency, as it avoids creating numerous intermediate string objects.

1class Solution {2    public List<String> validStrings(int n) {3        List<String> result = new ArrayList<>();4        if (n <= 0) return result;5        // Start the recursion for strings beginning with "0" and "1"6        backtrack(new StringBuilder("0"), n, result);7        backtrack(new StringBuilder("1"), n, result);8        return result;9    }10 11    private void backtrack(StringBuilder current, int n, List<String> result) {12        // Base case: a valid string of length n is found13        if (current.length() == n) {14            result.add(current.toString());15            return;16        }17 18        char lastChar = current.charAt(current.length() - 1);19 20        // If the last character was '0', the next must be '1'21        if (lastChar == '0') {22            current.append('1');23            backtrack(current, n, result);24            current.deleteCharAt(current.length() - 1); // Backtrack25        } 26        // If the last character was '1', the next can be '0' or '1'27        else { // lastChar == '1'28            // Option 1: Append '0'29            current.append('0');30            backtrack(current, n, result);31            current.deleteCharAt(current.length() - 1); // Backtrack32 33            // Option 2: Append '1'34            current.append('1');35            backtrack(current, n, result);36            current.deleteCharAt(current.length() - 1); // Backtrack37        }38    }39}