leetcode

commit 0af3b7c97c98d1e13c0170d900cbeb8d97f84ec5
parent d25a259a2484f14978ffe5e1cc350560e30445b0
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 25 Jun 2025 19:23:59 -0600

2311. longest binary subsequence less than or equal to k

Diffstat:
A
longest_binary_subseq_leq_k.c
 | 
30
++++++++++++++++++++++++++++++
A
longest_binary_subseq_leq_k.py
 | 
29
+++++++++++++++++++++++++++++

2 files changed, 59 insertions(+), 0 deletions(-)
diff --git a/longest_binary_subseq_leq_k.c 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
+}
diff --git a/longest_binary_subseq_leq_k.py b/longest_binary_subseq_leq_k.py
@@ -0,0 +1,29 @@
+# 2311. Longest Binary Subsequence Less Than or Equal to K
+
+"""
+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.
+"""
+
+
+class Solution(object):
+    def longestSubsequence(self, s, k):
+        """
+        :type s: str
+        :type k: int
+        :rtype: int
+        """
+        i = 0
+        while int(s[-i - 1 :], 2) <= k and i < 32 and i < len(s):
+            i += 1
+        return s[:-i].count("0") + i
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.longestSubsequence(s="1001010", k=5))
+    print(obj.longestSubsequence(s="00101001", k=1))