👹 Longest Binary Subsequence K – LeetCode 2311 (C++ | JavaScript | Python )

👋 Hey, binary sleuths! 🕵️‍♂️💡

Today, we dive into a clever bit manipulation puzzle — LeetCode 2311: Longest Binary Subsequence Less Than or Equal to K. It’s all about squeezing the longest subsequence out of a binary string that forms a number ≤ k. Let's decode this one together! 🧠

🧠 Problem Summary

You're given:

• A binary string s
  


• An integer k
  

You need to return the length of the longest subsequence of s such that:

• That subsequence forms a valid binary number ≤ k
  


• Leading zeroes are allowed


• Subsequence must respect the original order of characters

🧩 Intuition

To maximize the length of the subsequence:

• 
  Include all '0's — they do not increase the binary value.


• 
  Greedily add '1's from the right side — since binary is weighted from right to left, rightmost '1's have smaller impact.


• Stop adding when the resulting number exceeds k.

🧮 C++ Code

class Solution {

 public:

  int longestSubsequence(string s, int k) {

    int oneCount = 0;

    int num = 0;

    int pow = 1;



    // Take as many 1s as possible from the right.

    for (int i = s.length() - 1; i >= 0 && num + pow <= k; --i) {

      if (s[i] == '1') {

        ++oneCount;

        num += pow;

      }

      pow *= 2;

    }



    return ranges::count(s, '0') + oneCount;

  }

};

💻 JavaScript Code

var longestSubsequence = function(s, k) {

    let oneCount = 0;

    let num = 0;

    let pow = 1;



    for (let i = s.length - 1; i >= 0 && num + pow <= k; i--) {

        if (s[i] === '1') {

            oneCount++;

            num += pow;

        }

        pow *= 2;

    }



    const zeroCount = [...s].filter(ch => ch === '0').length;

    return zeroCount + oneCount;

};

🐍 Python Code

class Solution:

    def longestSubsequence(self, s: str, k: int) -> int:

        one_count = 0

        num = 0

        pow_ = 1



        for i in range(len(s) - 1, -1, -1):

            if s[i] == '1':

                if num + pow_ > k:

                    break

                one_count += 1

                num += pow_

            pow_ *= 2



        return s.count('0') + one_count

✅ Final Thoughts

This is a brilliant example of how understanding binary properties helps solve real problems. A few key insights let us:

• Avoid brute-force subsequence generation


• Use greedy and bitwise intuition


• Keep things simple and efficient

Drop a ❤️ if this helped, and keep sharpening your problem-solving toolkit! 💻✨

Happy coding! 🚀