Invariants

The concept of invariants is very powerful in computer science. Basically, an invariant is something that has certain immutable properties. For example, in the solution to the problem down below, the string current has the invariant property that it is always a "valid string", ready to be added to the retVal collection as soon as the length constraint is met. As we progress throughout the code, we need to assume and enforce the invariant property. Hence, since current is always valid, we can either append a "1" any time (remains valid), or append a "0" only if current is empty or ends with a "1", because if it ends with a "0" and we append a "0", we will break the invariant property. Code is down below, cheers, ACC.

Generate Binary Strings Without Adjacent Zeros - LeetCode

3211. Generate Binary Strings Without Adjacent Zeros

Medium

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

public IList ValidStrings(int n)
{
    IList retVal = new List();
    ValidStrings(n, "", retVal);
    return retVal;
}

private void ValidStrings(int n, string current, IList retVal)
{
    if (current.Length == n)
    {
        retVal.Add(current);
        return;
    }

    ValidStrings(n, current + "1", retVal);
    if (String.IsNullOrEmpty(current) || current.EndsWith("1"))
        ValidStrings(n, current + "0", retVal);
}