# Longest Binary Subsequence Less Than or Equal to K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-binary-subsequence-less-than-or-equal-to-k)
Canonical: https://scaleengineer.com/dsa/problems/longest-binary-subsequence-less-than-or-equal-to-k
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** String
---
## Problem
You are given a binary string `s` and a positive integer `k`.

Return _the length of the **longest** subsequence of_ `s` _that makes up a **binary** number less than or equal to_ `k`.

Note:

* The subsequence can contain **leading zeroes**.
* The empty string is considered to be equal to `0`.
* A **subsequence** is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

**Example 1:**

**Input:** s = "1001010", k = 5
**Output:** 5
**Explanation:** The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.

**Example 2:**

**Input:** s = "00101001", k = 1
**Output:** 6
**Explanation:** "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.

**Constraints:**

* `1 <= s.length <= 1000`
* `s[i]` is either `'0'` or `'1'`.
* `1 <= k <= 109`

# Approaches
## Dynamic Programming Approach
This approach uses dynamic programming to systematically find the solution. We build up the solution by considering each character of the string from right to left and for each character, we decide whether to include it in our subsequence or not. The state of our DP captures the minimum possible value for a given subsequence length.
**Time:** O(N^2), where N is the length of the string `s`. We have nested loops, one iterating through the string characters and the other through possible subsequence lengths. · **Space:** O(N), where N is the length of the string `s`. This is for the `dp` array and the precomputed `powers` array.
**Pros:** It is a systematic approach that guarantees finding the optimal solution.; It's a valid approach that passes within typical time limits for N up to 1000.
**Cons:** The O(N^2) time complexity is less efficient than the greedy approach.; The logic is more complex to implement correctly compared to the greedy solution.
### Explanation
Let `dp[l]` be the minimum value of a subsequence of length `l`. We initialize a `dp` array of size `n+1` where `dp[0]` is 0 and all other entries are set to a value larger than `k` to signify infinity. We then iterate through the input string `s` from right to left. For each character `s[i]`, we update the `dp` array. For every possible length `l`, the new `dp[l]` will be the minimum of its current value (by not taking `s[i]`) and the value obtained by taking `s[i]`. If we take `s[i]`, the new value is calculated based on `dp[l-1]` (the minimum value for a subsequence of length `l-1` from the rest of the string) and the character `s[i]` itself. If `s[i]` is '1', it adds `2^(l-1)` to the value. If it's '0', the value doesn't change. After processing all characters, we find the largest `l` for which `dp[l]` is not more than `k`.

```java
import java.util.Arrays;

class Solution {
    public int longestSubsequence(String s, int k) {
        int n = s.length();
        long[] dp = new long[n + 1];
        long infinity = k + 2L; // Use a value guaranteed to be > k
        Arrays.fill(dp, infinity);
        dp[0] = 0;

        long[] powers = new long[n + 1];
        powers[0] = 1;
        for (int i = 1; i <= n; i++) {
            powers[i] = powers[i - 1] * 2;
            if (powers[i] > k + 1) { // Cap power to avoid overflow
                powers[i] = infinity;
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int l = n; l >= 1; l--) {
                // Option 2: Take s[i] to form a subsequence of length l.
                // This requires a subsequence of length l-1 from s[i+1...].
                if (dp[l - 1] >= infinity) {
                    continue;
                }
                
                long val_if_taken;
                if (s.charAt(i) == '0') {
                    val_if_taken = dp[l - 1];
                } else { // s.charAt(i) == '1'
                    long power_of_2 = (l - 1 < powers.length) ? powers[l - 1] : infinity;
                    if (power_of_2 >= infinity || dp[l - 1] + power_of_2 > k) {
                        val_if_taken = infinity;
                    } else {
                        val_if_taken = dp[l - 1] + power_of_2;
                    }
                }
                // Option 1 (not taking s[i]) is implicitly handled as dp[l] is the old value.
                dp[l] = Math.min(dp[l], val_if_taken);
            }
        }

        for (int l = n; l >= 0; l--) {
            if (dp[l] <= k) {
                return l;
            }
        }
        return 0;
    }
}
```
### Algorithm
1. Define a DP state `dp[l]` as the minimum possible numerical value of a subsequence of length `l`.
2. Initialize a `dp` array of size `n+1`, where `n` is the length of `s`. Set `dp[0] = 0` and all other `dp[l]` to a value larger than `k` (representing infinity).
3. Iterate through the string `s` from right to left, from `i = n-1` down to `0`.
4. In each iteration `i`, update the `dp` array. For each length `l` from `n` down to `1`, we consider two choices for `s[i]`:
    a. **Don't include `s[i]`**: The minimum value for a subsequence of length `l` remains `dp[l]` (which holds the value from considering the suffix `s[i+1:]`).
    b. **Include `s[i]`**: To form a subsequence of length `l`, we must have formed a subsequence of length `l-1` from the suffix `s[i+1:]`. The minimum value for this is `dp[l-1]`. 
        - If `s[i] == '0'`, the new value is `dp[l-1]`.
        - If `s[i] == '1'`, the new value is `dp[l-1] + 2^(l-1)`.
    We update `dp[l]` with the minimum of these two choices.
5. After iterating through the entire string, the `dp` array holds the minimum values for subsequences of all possible lengths.
6. Find the largest length `l` such that `dp[l] <= k`.

## Greedy Approach
A more efficient greedy strategy can solve this problem in linear time. The key insight is that to maximize the subsequence's length while keeping its value low, we should prioritize including all zeros and the rightmost ones from the original string. This is because zeros are 'cheap' for length, and ones at rightmost positions contribute the least to the numerical value.
**Time:** O(N), where N is the length of the string `s`, because we perform a single pass through the string. · **Space:** O(1), as we only use a few variables to store the current length and value.
**Pros:** Extremely efficient with O(N) time complexity.; Uses constant extra space, making it very memory-efficient.; The logic is relatively simple to implement once the greedy strategy is understood.
**Cons:** The greedy choice might not be immediately obvious without analyzing the problem structure.
### Explanation
We can build the longest subsequence by making greedy choices. We iterate through the string `s` from right to left. We maintain a `length` of the subsequence found so far and its numerical `value`.

- When we encounter a '0', we can always add it to our subsequence. This increases the length by one and can be considered a leading zero or a zero bit, neither of which will violate the condition `value <= k` in a detrimental way compared to not picking it. So, we always increment the length.
- When we encounter a '1', we consider adding it. If we have already chosen `length` characters from the right part of `s`, this '1' would be at bit position `length` in our subsequence. Its value is `2^length`. We can only add this '1' if the new total `value + 2^length` does not exceed `k`. If it does, we add it to our subsequence (increment `length` and update `value`); otherwise, we must skip it.

This process ensures we pick up all possible zeros and the '1's that contribute the least to the total value, thus maximizing the length under the given constraint.

```java
class Solution {
    public int longestSubsequence(String s, int k) {
        int length = 0;
        long value = 0;
        int n = s.length();

        for (int i = n - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '0') {
                length++;
            } else { // c == '1'
                // The bit position for this '1' would be 'length'.
                // If length is too large, 2^length will exceed k.
                // k <= 10^9 < 2^30. So if length >= 31, 2^length > k.
                if (length >= 31) {
                    continue; // Cannot add this '1', its value is too high.
                }
                
                long power_of_2 = 1L << length;
                if (value + power_of_2 <= k) {
                    value += power_of_2;
                    length++;
                }
            }
        }
        return length;
    }
}
```
### Algorithm
1. Initialize `length = 0` and `value = 0`.
2. Iterate through the string `s` from right to left (from index `n-1` down to `0`).
3. For each character `s[i]`:
    a. If `s[i] == '0'`, it's always optimal to include it. It increases length without adding to the value part of the number we are tracking. So, increment `length`.
    b. If `s[i] == '1'`, we check if we can include it. The position of this '1' in the subsequence we are building would be `length`. Its numerical contribution would be `2^length`.
    c. If `value + 2^length <= k`, we include the '1' by adding `2^length` to `value` and incrementing `length`.
    d. To avoid overflow with `2^length`, we can note that if `length` is large (e.g., >= 31, since `k < 2^30`), `2^length` will surely be greater than `k`, so we can't add the '1'.
4. After the loop, `length` will hold the length of the longest valid subsequence.

# Solutions
### CSharp

```csharp
public class Solution {
    public int LongestSubsequence(string s, int k) {
        int ans = 0, v = 0;
        for (int i = s.Length - 1; i >= 0; --i) {
            if (s[i] == '0') {
                ++ans;
            } else if (ans < 30 && (v | 1 << ans) <= k) {
                v |= 1 << ans;
                ++ans;
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int longestSubsequence(String s, int k) {
    int ans = 0, v = 0;
    for (int i = s.length() - 1; i >= 0; --i) {
      if (s.charAt(i) == '0') {
        ++ans;
      } else if (ans < 30 && (v | 1 << ans) <= k) {
        v |= 1 << ans;
        ++ans;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @param {number} k * @return {number} */ var longestSubsequence = function ( s , k ) { let ans = 0 ; for ( let i = s . length - 1 , v = 0 ; ~ i ; -- i ) { if ( s [ i ] == ' 0 ' ) { ++ ans ; } else if ( ans < 30 && ( v | ( 1 << ans )) <= k ) { v |= 1 << ans ; ++ ans ; } } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  int longestSubsequence(string s, int k) {
    int ans = 0, v = 0;
    for (int i = s.size() - 1; ~i; --i) {
      if (s[i] == '0') {
        ++ans;
      } else if (ans < 30 && (v | 1 << ans) <= k) {
        v |= 1 << ans;
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestSubsequence(self, s: str, k: int) -> int: ans = v = 0 for c in s[:: - 1]: if c == "0": ans += 1 elif ans < 30 and (v | 1 << ans) <= k: v |= 1 << ans ans += 1 return ans

```