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.


&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 1000
	s[i] is either '0' or '1'.
	1 &lt;= k &lt;= 109


class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
    
        end, n  = len(s)-1, s.count("0")    
        while end >=0 and  int(s[end:], 2)<= k:
            end-=1
        return n+ s[end+1:].count("1")
        
class Solution {
    public int longestSubsequence(String s, int k) {
        int numOfZeros = 0;
        int numOfOnes = 0;
        
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '0'){
                numOfZeros++;
            }
        }
        int sum = 0;
        for(int i = s.length() - 1; i >= 0; i--){
            char ch = s.charAt(i);
            if(ch == '1'){
                double val = Math.pow(2, s.length() - i - 1);
                sum += val;
                if(sum <= k){
                    numOfOnes++;
                }
            }
        }
        return numOfZeros + numOfOnes;
    }
}
class Solution {
public:
    int ans = 0;
    int f(int i,int size, int sum, string &s, vector<vector<int>>&dp){
        if(i<0){
            return 0;
        }
        if(dp[i][size] != -1){
            return dp[i][size];
        }
        int no = f(i-1,size,sum,s,dp);
        int yes = 0;
        if((sum-(s[i]-'0')*pow(2,size)) >=0){
            yes = 1+ f(i-1,size+1,(sum-(s[i]-'0')*pow(2,size)),s,dp);
        }
        return dp[i][size]=max(no,yes);
    }
    int longestSubsequence(string s, int k) {

        int n = s.size();
        vector<vector<int>>dp(n,vector<int>(n,-1));
        return f(n-1,0,k,s,dp);

    }
};
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */

var longestSubsequence = function(s, k) {
    let count = 0;
    let j = s.length - 1; // starting from the last digit
    let i = 0; // binary number position
    let acc = 0;

    while(j >= 0){
        let positionNumber = Number(s[j]) * Math.pow(2, i);
        j--;
        i++;
        if(acc + positionNumber > k) continue;

        acc += positionNumber;
        count++;
    }

    return count;
};
Longest Binary Subsequence Less Than or Equal to K