Skip to content

← leetcode

Longest Binary Subsequence Less Than or Equal to K

· Medium

LeetCode problem 2311

You can basically view this as a greedy problem.

Since we want to maximise the subsequence of s that makes up a binary number smaller or equal to k, the 1 bits we want to include into the subsequence should be the ones that are furthest to the right.

Therefore, our algorithm should iterate from the end of s to the start of s. In the process, you will see either 0 or 1 values:

  • if you see 0, just add 11 to the length of the longest subsequence (it has no effect)
  • if you see 1, add the base-10 counterpart to a running-sum and check if the running-sum is smaller than or equal to k
    • if it is, then you can add 11 to the length of the longest subsequence
    • else, you can just continue

code

class Solution {
public:
    int longestSubsequence(string s, int k) {
        long long current = 0;
        long long counter = 1;

        int ans = 0;
        int i = s.size()-1;
        for (; i >= 0 && counter <= k; --i) {
            if (s[i] == '1') {
                if (current + counter <= k) {
                    current += counter;
                    ++ans;
                } else {
                    break;
                }
            } else {
                ++ans;
            }
            counter *= 2;
        }
        for (; i >= 0; --i) {
            if (s[i] == '0') {
                ++ans;
            }
        }
        return ans;
    }
};

complexity

  • Time: O(n)
  • Space: O(1)

time taken

  • 10 minutes and 51 seconds