2311: Longest-Binary-Subsequence-Less-Than-or-Equal-to-K
Medium

table of contents

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:

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 taken