Welcome to Subscribe On Youtube

3955. Valid Binary Strings With Cost Limit

Description

You are given two integers n and k.

The cost of a binary string s is defined as the sum of all indices i (0-based) such that s[i] == '1'.

A binary string is considered valid if:

• It does not contain two consecutive '1' characters.
• Its cost is less than or equal to k.

Return a list of all valid binary strings of length n in any order.

 

Example 1:

Input: n = 3, k = 1

Output: ["000","010","100"]

Explanation:

The binary strings of length 3 without consecutive '1' characters are:

• "000" : cost = 0
• "100" : cost = 0
• "010" : cost = 1
• "001" : cost = 2
• "101" : cost = 0 + 2 = 2

Among these, the strings with cost less than or equal to k = 1 are "000", "010" and "100".

Thus, the valid strings are ["000", "010", "100"].

Example 2:

Input: n = 1, k = 0

Output: ["0","1"]

Explanation:

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

Thus the answer is ["0", "1"].

 

Constraints:

• 1 <= n <= 12
• 0 <= k <= n * (n - 1) / 2

Solutions

Solution 1: DFS

We want to generate binary strings of length $n$ that satisfy the following conditions:

• The sum of the positions $i$ (0-indexed) of each 1 does not exceed $k$, which can be expressed as:

\[\sum_{i \mid s_i = 1} i \le k\]

• No two 1s can be adjacent to each other.

Therefore, we design a recursive function $\text{dfs}(i, tot)$, where:

• $i$ represents the current position being processed in the string;
• $tot$ represents the sum of the indices of all 1s placed so far.

Recursive Logic

1. Base Case (Termination Condition)

When $i \ge n$, it means a string of length $n$ has been fully constructed. At this point, add the current path to the answer list.

2. Choosing 0

A 0 can always be placed at the current position. We recursively call $\text{dfs}(i + 1, tot)$. Since a 0 is placed, the total sum $tot$ remains unchanged.

3. Choosing 1

A 1 can be placed at the current position only if both of the following conditions are met: the previous character does not exist (or is 0), and $tot + i \le k$. In this case, we recursively call $\text{dfs}(i + 1, tot + i)$.

4. Backtracking

After each recursive call returns, we undo the current choice to restore the state before entering the recursion, allowing the algorithm to explore other possible combinations.

The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      private int n;
      private int k;
      private List<String> ans;
      private StringBuilder path;
  
      public List<String> generateValidStrings(int n, int k) {
          this.n = n;
          this.k = k;
          ans = new ArrayList<>();
          path = new StringBuilder();
  
          dfs(0, 0);
  
          return ans;
      }
  
      private void dfs(int i, int tot) {
          if (i >= n) {
              ans.add(path.toString());
              return;
          }
  
          path.append('0');
          dfs(i + 1, tot);
          path.deleteCharAt(path.length() - 1);
  
          if ((path.isEmpty() || path.charAt(path.length() - 1) == '0') && tot + i <= k) {
              path.append('1');
              dfs(i + 1, tot + i);
              path.deleteCharAt(path.length() - 1);
          }
      }
  }
  

• class Solution {
  public:
      vector<string> generateValidStrings(int n, int k) {
          vector<string> ans;
          string path;
  
          auto dfs = [&](this auto&& dfs, int i, int tot) -> void {
              if (i >= n) {
                  ans.push_back(path);
                  return;
              }
  
              path.push_back('0');
              dfs(i + 1, tot);
              path.pop_back();
  
              if ((path.empty() || path.back() == '0') && tot + i <= k) {
                  path.push_back('1');
                  dfs(i + 1, tot + i);
                  path.pop_back();
              }
          };
  
          dfs(0, 0);
  
          return ans;
      }
  };
  

• class Solution:
      def generateValidStrings(self, n: int, k: int) -> list[str]:
          def dfs(i: int, tot: int):
              if i >= n:
                  ans.append("".join(path))
                  return
              path.append("0")
              dfs(i + 1, tot)
              path.pop()
              if (not path or path[-1] == "0") and tot + i <= k:
                  path.append("1")
                  dfs(i + 1, tot + i)
                  path.pop()
  
          ans = []
          path = []
          dfs(0, 0)
          return ans
  
  

• func generateValidStrings(n int, k int) []string {
  	ans := []string{}
  	path := make([]byte, 0, n)
  
  	var dfs func(int, int)
  	dfs = func(i, tot int) {
  		if i >= n {
  			ans = append(ans, string(path))
  			return
  		}
  
  		path = append(path, '0')
  		dfs(i+1, tot)
  		path = path[:len(path)-1]
  
  		if (len(path) == 0 || path[len(path)-1] == '0') && tot+i <= k {
  			path = append(path, '1')
  			dfs(i+1, tot+i)
  			path = path[:len(path)-1]
  		}
  	}
  
  	dfs(0, 0)
  
  	return ans
  }
  

• function generateValidStrings(n: number, k: number): string[] {
      const ans: string[] = [];
      const path: string[] = [];
  
      const dfs = (i: number, tot: number): void => {
          if (i >= n) {
              ans.push(path.join(''));
              return;
          }
  
          path.push('0');
          dfs(i + 1, tot);
          path.pop();
  
          if ((path.length === 0 || path[path.length - 1] === '0') && tot + i <= k) {
              path.push('1');
              dfs(i + 1, tot + i);
              path.pop();
          }
      };
  
      dfs(0, 0);
  
      return ans;
  }
  
  

All Problems

All Solutions