leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

longest_binary_subseq_leq_k.c (972B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 2311. Longest Binary Subsequence Less Than or Equal to K
#include "leetcode.h"

/*
 * 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 zeros, the
 * empty string is considered to be equal to 0, and 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.
 */

int longestSubsequence(char *s, int k) {
  int ans = 0, cost = 1, n = strlen(s);
  for (int i = n - 1; i >= 0; --i) {
    if (s[i] == '0' || cost <= k) {
      k -= cost * (s[i] - '0');
      ans++;
    }
    if (cost <= k)
      cost *= 2;
  }
  return ans;
}

int main() {
  char *s1 = "1001010", *s2 = "00101001";
  printf("%d\n", longestSubsequence(s1, 5)); // expect: 5
  printf("%d\n", longestSubsequence(s2, 1)); // expect: 6
}