diff options
author | Jack Sangdahl <[email protected]> | 2025-06-25 19:23:59 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-25 19:23:59 -0600 |
commit | 0af3b7c97c98d1e13c0170d900cbeb8d97f84ec5 (patch) | |
tree | 68576d703ade1715f50ffc0fe2237286aa6a42ca /longest_binary_subseq_leq_k.c | |
parent | d25a259a2484f14978ffe5e1cc350560e30445b0 (diff) | |
download | leetcode-0af3b7c97c98d1e13c0170d900cbeb8d97f84ec5.tar.gz leetcode-0af3b7c97c98d1e13c0170d900cbeb8d97f84ec5.zip |
2311. longest binary subsequence less than or equal to k
Diffstat (limited to 'longest_binary_subseq_leq_k.c')
-rw-r--r-- | longest_binary_subseq_leq_k.c | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/longest_binary_subseq_leq_k.c b/longest_binary_subseq_leq_k.c new file mode 100644 index 0000000..7920e7d --- /dev/null +++ b/longest_binary_subseq_leq_k.c @@ -0,0 +1,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 +} |