aboutsummaryrefslogtreecommitdiff
path: root/longest_binary_subseq_leq_k.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-25 19:23:59 -0600
committerJack Sangdahl <[email protected]>2025-06-25 19:23:59 -0600
commit0af3b7c97c98d1e13c0170d900cbeb8d97f84ec5 (patch)
tree68576d703ade1715f50ffc0fe2237286aa6a42ca /longest_binary_subseq_leq_k.c
parentd25a259a2484f14978ffe5e1cc350560e30445b0 (diff)
downloadleetcode-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.c30
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
+}