Longest Binary Subsequence Less Than or Equal to K
MedPrompt
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 <= 1000s[i]is either'0'or'1'.1 <= k <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a DP state
dp[l]as the minimum possible numerical value of a subsequence of lengthl. - Initialize a
dparray of sizen+1, wherenis the length ofs. Setdp[0] = 0and all otherdp[l]to a value larger thank(representing infinity). - Iterate through the string
sfrom right to left, fromi = n-1down to0. - In each iteration
i, update thedparray. For each lengthlfromndown to1, we consider two choices fors[i]: a. Don't includes[i]: The minimum value for a subsequence of lengthlremainsdp[l](which holds the value from considering the suffixs[i+1:]). b. Includes[i]: To form a subsequence of lengthl, we must have formed a subsequence of lengthl-1from the suffixs[i+1:]. The minimum value for this isdp[l-1]. - Ifs[i] == '0', the new value isdp[l-1]. - Ifs[i] == '1', the new value isdp[l-1] + 2^(l-1). We updatedp[l]with the minimum of these two choices. - After iterating through the entire string, the
dparray holds the minimum values for subsequences of all possible lengths. - Find the largest length
lsuch thatdp[l] <= k.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.