[Solved] Longest Binary Subsequence Less Than or Equal to K Case Contest Problem

Longest Binary Subsequence Less Than or Equal to K: 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.

Longest Binary Subsequence Less Than or Equal to K LeetCode

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

Solution 1: DP solution

dp[i] means the minimum value of subsequence with length i

Time O(n^2)
Space O(n)

    public int longestSubsequence(String s, int k) {
        int dp[] = new int[s.length() + 1], j = 0;
        for (char c : s.toCharArray()) {
            if (dp[j] * 2 + c - '0' <= k) {
                dp[j + 1] = dp[j] * 2 + c - '0';
                j++;
            }
            for (int i = j; i > 0; --i)
                dp[i] = Math.min(dp[i], dp[i - 1] * 2 + c - '0');
        }
        return j;
    }

    int longestSubsequence(string s, int k) {
        int dp[1010] = {}, j = 0;
        for (char& v : s) {
            if (dp[j] * 2 + v - '0' <= k)
                dp[++j] = dp[j] * 2 + v - '0';
            for (int i = j; i > 0; --i)
                dp[i] = min(dp[i], dp[i - 1] * 2 + v - '0');
        }
        return j;
    }

    def longestSubsequence(self, s, k):
        dp = [0]
        for v in map(int, s):
            if dp[-1] * 2 + v <= k:
                dp.append(dp[-1] * 2 + v)
            for i in range(len(dp) - 1, 0, -1):
                dp[i] = min(dp[i], dp[i - 1] * 2 + v)
        return len(dp) - 1

Solution 2: One Pass

We greedly take all 0s and try to take as many 1s as possible.
To take the 1 with a smaller cost, we take the 1s from the rightmost.

Time O(n)
Space O(1)

    public int longestSubsequence(String s, int k) {
        int res = 0, cost = 1, n = s.length();
        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == '0' || cost <= k) {
                k -= cost * (s.charAt(i) - '0');
                res++;
            }
            if (cost <= k)
                cost *= 2;
        }
        return res;
    }

    int longestSubsequence(string s, int k) {
        int res = 0, cost = 1, n = s.size();
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '0' || cost <= k) {
                k -= cost * (s[i] - '0');
                res++;
            }
            if (cost <= k)
                cost *= 2;
        }
        return res;
    }

    def longestSubsequence(self, s, k):
        i = 0
        while int(s[-i-1:], 2) <= k and i < 32 and i < len(s):
            i += 1
        return s[:-i].count('0') + i

Happy Learning – If you require any further information, feel free to contact me.