# 2311. Longest Binary Subsequence Less Than or Equal to K
###### tags: `Leetcode` `Medium` `Bit Manipulation` `Greedy`
Link: https://leetcode.com/problems/longest-binary-subsequence-less-than-or-equal-to-k/
## 思路
先数出零的个数当作base
然后从右往左加1 一直加到现在的数字超过k为止 就可以得到最长的subsequence
这里要注意 回圈里面不能写成

for(int i=n-1; i>=0; i--){
    if(s.charAt(i)=='1'){
        if(curr+(1<<(n-1-i))<=k){
            currLen++;
            curr += 1<<(n-1-i);
        }
        else break;
    }
}

因为这样如果```1<<(n-1-i)```超出int范围变成负数了 还可以往上继续加 最长的subsequence就会变得更长
## Code

class Solution {
    public int longestSubsequence(String s, int k) {
        int countZero = 0;
        int n = s.length();
        for(int i=0; i<n; i++){
            if(s.charAt(i)=='0') countZero++;
        }
        int curr = 0;
        int currLen = countZero;
        int pow = 1;
        for(int i=n-1; i>=0; i--){
            if(curr+pow>k) break;
            if(s.charAt(i)=='1'){
                if(curr+(1<<(n-1-i))<=k){
                    currLen++;
                    curr += 1<<(n-1-i);
                }
            }
            pow<<=1;
        }
        return currLen;
    }
}