Longest Binary Subsequence Less Than or Equal to K

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.

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.

1import java.util.Arrays;2 3class Solution {4    public int longestSubsequence(String s, int k) {5        int n = s.length();6        long[] dp = new long[n + 1];7        long infinity = k + 2L; // Use a value guaranteed to be > k8        Arrays.fill(dp, infinity);9        dp[0] = 0;10 11        long[] powers = new long[n + 1];12        powers[0] = 1;13        for (int i = 1; i <= n; i++) {14            powers[i] = powers[i - 1] * 2;15            if (powers[i] > k + 1) { // Cap power to avoid overflow16                powers[i] = infinity;17            }18        }19 20        for (int i = n - 1; i >= 0; i--) {21            for (int l = n; l >= 1; l--) {22                // Option 2: Take s[i] to form a subsequence of length l.23                // This requires a subsequence of length l-1 from s[i+1...].24                if (dp[l - 1] >= infinity) {25                    continue;26                }27                28                long val_if_taken;29                if (s.charAt(i) == '0') {30                    val_if_taken = dp[l - 1];31                } else { // s.charAt(i) == '1'32                    long power_of_2 = (l - 1 < powers.length) ? powers[l - 1] : infinity;33                    if (power_of_2 >= infinity || dp[l - 1] + power_of_2 > k) {34                        val_if_taken = infinity;35                    } else {36                        val_if_taken = dp[l - 1] + power_of_2;37                    }38                }39                // Option 1 (not taking s[i]) is implicitly handled as dp[l] is the old value.40                dp[l] = Math.min(dp[l], val_if_taken);41            }42        }43 44        for (int l = n; l >= 0; l--) {45            if (dp[l] <= k) {46                return l;47            }48        }49        return 0;50    }51}

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.

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.

1class Solution {2    public int longestSubsequence(String s, int k) {3        int length = 0;4        long value = 0;5        int n = s.length();6 7        for (int i = n - 1; i >= 0; i--) {8            char c = s.charAt(i);9            if (c == '0') {10                length++;11            } else { // c == '1'12                // The bit position for this '1' would be 'length'.13                // If length is too large, 2^length will exceed k.14                // k <= 10^9 < 2^30. So if length >= 31, 2^length > k.15                if (length >= 31) {16                    continue; // Cannot add this '1', its value is too high.17                }18                19                long power_of_2 = 1L << length;20                if (value + power_of_2 <= k) {21                    value += power_of_2;22                    length++;23                }24            }25        }26        return length;27    }28}