longest-binary-subsequence-less-than-or-equal-to-k

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a binary string <code>s</code> and a positive integer <code>k</code>.

Return the length of the longest subsequence of <code>s</code> that makes up a binary number less than or equal to <code>k</code>.

Note:

<ul>
	<li>The subsequence can contain leading zeroes.</li>
	<li>The empty string is considered to be equal to <code>0</code>.</li>
	<li>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.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: s = &quot;1001010&quot;, k = 5
Output: 5
Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is &quot;00010&quot;, as this number is equal to 2 in decimal.
Note that &quot;00100&quot; and &quot;00101&quot; are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.
</pre>

Example 2:

<pre>
Input: s = &quot;00101001&quot;, k = 1
Output: 6
Explanation: &quot;000001&quot; is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= k &lt;= 109</code></li>
</ul>

longestSubsequence

Longest Binary Subsequence Less Than or Equal to K

Maximum Binary String After Change

maximum-binary-string-after-change

修改后的最大二进制字符串

Greedy

Memoization

String

Dynamic Programming

给你一个二进制字符串&nbsp;<code>s</code>&nbsp;和一个正整数&nbsp;<code>k</code>&nbsp;。

请你返回 <code>s</code>&nbsp;的 最长&nbsp;子序列，且该子序列对应的 二进制&nbsp;数字小于等于 <code>k</code>&nbsp;。

注意：

<ul>
	<li>子序列可以有 前导 0&nbsp;。</li>
	<li>空字符串视为&nbsp;<code>0</code>&nbsp;。</li>
	<li>子序列&nbsp;是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。</li>
</ul>

&nbsp;

示例 1：

<pre>输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。
</pre>

示例 2：

<pre>输入：s = "00101001", k = 1
输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s[i]</code> 要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code> 。</li>
	<li><code>1 &lt;= k &lt;= 109</code></li>
</ul>