跳转至

2311. 小于等于 K 的最长二进制子序列

来源第 298 场周赛 Q3难度中等分数1839

题目描述

给你一个二进制字符串 s 和一个正整数 k 。

请你返回 s 的 最长 子序列的长度，且该子序列对应的 二进制 数字小于等于 k 。

注意：

  • 子序列可以有 前导 0 。
  • 空字符串视为 0 。
  • 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

 

示例 1：

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

示例 2：

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

 

提示：

  • 1 <= s.length <= 1000
  • s[i] 要么是 '0' ，要么是 '1' 。
  • 1 <= k <= 109

解法

方法一：贪心

思考

子序列对应的数值须 \(\le k\)。\(s\) 长至多 \(1000\)，枚举子集不可行。所有 \(0\) 不增加数值，理应全部保留。

高位的 \(1\) 代价更大，因此从右向左考虑能否再收一个 \(1\)。用当前已选长度作为该 \(1\) 的权值下标，若并入后仍 \(\le k\) 则收下。超过约 \(30\) 位必然大于 \(k\)，可直接跳过。

最长二进制子序列必然包含原字符串中所有的 \(0\)，在此基础上，我们从右到左遍历 \(s\)，若遇到 \(1\)，判断子序列能否添加 \(1\)，使得子序列对应的二进制数字 \(v \leq k\)。

时间复杂度 \(O(n)\)，其中 \(n\) 为字符串 \(s\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        ans = v = 0
        for c in s[::-1]:
            if c == "0":
                ans += 1
            elif ans < 30 and (v | 1 << ans) <= k:
                v |= 1 << ans
                ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int longestSubsequence(String s, int k) {
        int ans = 0, v = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            if (s.charAt(i) == '0') {
                ++ans;
            } else if (ans < 30 && (v | 1 << ans) <= k) {
                v |= 1 << ans;
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int longestSubsequence(string s, int k) {
        int ans = 0, v = 0;
        for (int i = s.size() - 1; ~i; --i) {
            if (s[i] == '0') {
                ++ans;
            } else if (ans < 30 && (v | 1 << ans) <= k) {
                v |= 1 << ans;
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func longestSubsequence(s string, k int) (ans int) {
    for i, v := len(s)-1, 0; i >= 0; i-- {
        if s[i] == '0' {
            ans++
        } else if ans < 30 && (v|1<<ans) <= k {
            v |= 1 << ans
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function longestSubsequence(s: string, k: number): number {
    let ans = 0;
    for (let i = s.length - 1, v = 0; ~i; --i) {
        if (s[i] == '0') {
            ++ans;
        } else if (ans < 30 && (v | (1 << ans)) <= k) {
            v |= 1 << ans;
            ++ans;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubsequence = function (s, k) {
    let ans = 0;
    for (let i = s.length - 1, v = 0; ~i; --i) {
        if (s[i] == '0') {
            ++ans;
        } else if (ans < 30 && (v | (1 << ans)) <= k) {
            v |= 1 << ans;
            ++ans;
        }
    }
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Solution {
    public int LongestSubsequence(string s, int k) {
        int ans = 0, v = 0;
        for (int i = s.Length - 1; i >= 0; --i) {
            if (s[i] == '0') {
                ++ans;
            } else if (ans < 30 && (v | 1 << ans) <= k) {
                v |= 1 << ans;
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn longest_subsequence(s: String, k: i32) -> i32 {
        let mut ans = 0;
        let mut v = 0;
        let s = s.as_bytes();
        for i in (0..s.len()).rev() {
            if s[i] == b'0' {
                ans += 1;
            } else if ans < 30 && (v | (1 << ans)) <= k {
                v |= 1 << ans;
                ans += 1;
            }
        }
        ans
    }
}

评论