• 📅 Date: 26th June, 2025
• Topics: String, Dynamic Programming, Greedy, Memoization
• Leetcode Link

---

🔍 Problem Summary

Given a binary string s and integer k, find the length of the longest subsequence (not necessarily contiguous) of s that represents a binary number ≤ k.

Python Code

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        """
        Find the length of the longest subsequence that forms a binary number <= k.

        Key insights:
        1. All zeros can be included (leading zeros don't change value)
        2. For ones, we should greedily pick from right to left (least significant first)
        3. This maximizes the count while staying within the limit

        Time: O(n), Space: O(1)
        """
        zeros = s.count('0')  # All zeros can always be included

        if k == 0:
            return zeros

        current_value = 0
        ones_count = 0
        bit_value = 1

        for i in range(len(s) - 1, -1, -1):
            if s[i] == '1':
                if current_value + bit_value <= k:
                    current_value += bit_value
                    ones_count += 1

            bit_value *= 2
            if bit_value > k:
                break

        return zeros + ones_count

🔪 Key Insights

• All '0' characters can be included since they don't increase the binary value
• Greedily include '1' bits starting from the least significant position (rightmost)
• Stop once the cumulative value exceeds k
• Efficient: no need to generate all subsequences

---

📊 Summary Table