aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--longest_binary_subseq_leq_k.c30
-rw-r--r--longest_binary_subseq_leq_k.py29
2 files changed, 59 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
+}
diff --git a/longest_binary_subseq_leq_k.py b/longest_binary_subseq_leq_k.py
new file mode 100644
index 0000000..e07204a
--- /dev/null
+++ 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))