Longest Binary Subsequence Less Than or Equal to K

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7


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:

1
2
3
4
5
6


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.

Solution

Method 1 – Greedy + Bitwise Simulation

Intuition

To maximize the length of the subsequence, we want to include as many ‘0’s as possible (since leading zeros don’t increase the value), and then greedily include ‘1’s from the right (least significant bits) as long as the resulting binary value does not exceed k.

Approach

Count all ‘0’s in the string s since they can always be included.
Traverse the string from right to left (least significant to most significant bit).
For each ‘1’, try to include it if the resulting value does not exceed k.

Keep track of the current value using bitwise operations.
Stop including ‘1’s if adding another would exceed k or if the bit position exceeds 60 (since k can be up to 10^9).

The answer is the count of all ‘0’s plus the number of ‘1’s included.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
   int longestSubsequence(string s, int k) {
      int n = s.size(), ans = 0, zeros = 0;
      for (char c : s) if (c == '0') zeros++;
      long long val = 0, pow2 = 1;
      int ones = 0;
      for (int i = n - 1; i >= 0; --i) {
        if (s[i] == '1') {
           if (val + pow2 <= k) {
              val += pow2;
              ones++;
           }
        }
        if (pow2 > k) break;
        pow2 <<= 1;
      }
      return zeros + ones;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func longestSubsequence(s string, k int) int {
   n, zeros, ones := len(s), 0, 0
   for _, c := range s {
      if c == '0' {
        zeros++
      }
   }
   val, pow2 := 0, 1
   for i := n - 1; i >= 0; i-- {
      if s[i] == '1' {
        if val+pow2 <= k {
           val += pow2
           ones++
        }
      }
      if pow2 > k {
        break
      }
      pow2 <<= 1
   }
   return zeros + ones
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
   public int longestSubsequence(String s, int k) {
      int n = s.length(), zeros = 0, ones = 0;
      for (char c : s.toCharArray()) if (c == '0') zeros++;
      long val = 0, pow2 = 1;
      for (int i = n - 1; i >= 0; --i) {
        if (s.charAt(i) == '1') {
           if (val + pow2 <= k) {
              val += pow2;
              ones++;
           }
        }
        if (pow2 > k) break;
        pow2 <<= 1;
      }
      return zeros + ones;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
   fun longestSubsequence(s: String, k: Int): Int {
      var zeros = 0
      for (c in s) if (c == '0') zeros++
      var valNum = 0L
      var pow2 = 1L
      var ones = 0
      for (i in s.length - 1 downTo 0) {
        if (s[i] == '1') {
           if (valNum + pow2 <= k) {
              valNum += pow2
              ones++
           }
        }
        if (pow2 > k) break
        pow2 = pow2 shl 1
      }
      return zeros + ones
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
   def longestSubsequence(self, s: str, k: int) -> int:
      zeros = s.count('0')
      val = 0
      pow2 = 1
      ones = 0
      for c in reversed(s):
        if c == '1':
           if val + pow2 <= k:
              val += pow2
              ones += 1
        if pow2 > k:
           break
        pow2 <<= 1
      return zeros + ones

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


impl Solution {
   pub fn longest_subsequence(s: String, k: i32) -> i32 {
      let bytes = s.as_bytes();
      let mut zeros = bytes.iter().filter(|&&c| c == b'0').count() as i32;
      let mut val = 0i64;
      let mut pow2 = 1i64;
      let mut ones = 0;
      for &c in bytes.iter().rev() {
        if c == b'1' {
           if val + pow2 <= k as i64 {
              val += pow2;
              ones += 1;
           }
        }
        if pow2 > k as i64 {
           break;
        }
        pow2 <<= 1;
      }
      zeros + ones
   }
}

Complexity

⏰ Time complexity: O(n) (single pass through the string)
🧺 Space complexity: O(1) (constant extra space)

Problem#

Examples#

Solution#

Method 1 – Greedy + Bitwise Simulation#

Intuition#

Approach#

Code#

Complexity#