【教3妹学编程-算法题】最长平衡子字符串
  96AOqGW9dKgh 2023年12月06日 28 0


【教3妹学编程-算法题】最长平衡子字符串_字符串


3妹:呜呜,烦死了, 脸上长了一个痘

2哥 : 不要在意这些细节嘛,不用管它,过两天自然不就好了。

3妹:切,你不懂,影响这两天的心情哇。

2哥 : 我看你是不急着找工作了啊, 工作那么辛苦,哪还有时间想这些啊。

3妹:说到找工作,我又要去刷题了。

2哥:我给你出一道关于美丽的题吧,让你的心情美丽美丽~

3妹:2哥真能忽悠,心情好了让刷题,心情不好也让刷题,那请问啥时候不用刷题勒?

2哥:是进亦忧,退亦忧。然则何时而乐耶?其必曰:刷完之后就不用刷了。哈哈

3妹:切,刷完了2哥要请吃饭!

题目:

给你一个仅由 0 和 1 组成的二进制字符串 s 。

如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量,则认为 s 的这个子字符串是平衡子字符串。请注意,空子字符串也视作平衡子字符串。

返回 s 中最长的平衡子字符串长度。

子字符串是字符串中的一个连续字符序列。

示例 1:

输入:s = “01000111”
输出:6
解释:最长的平衡子字符串是 “000111” ,长度为 6 。
示例 2:

输入:s = “00111”
输出:4
解释:最长的平衡子字符串是 “0011” ,长度为 4 。
示例 3:

输入:s = “111”
输出:0
解释:除了空子字符串之外不存在其他平衡子字符串,所以答案为 0 。

提示:

1 <= s.length <= 50
‘0’ <= s[i] <= ‘1’

思路:

【教3妹学编程-算法题】最长平衡子字符串_算法_02

计数,遍历时,不停更新平衡字符串的最大长度

java代码:

class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int res = 0;
        int n = s.length();
        int[] count = new int[2];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                count[1]++;
                res = Math.max(res, 2 * Math.min(count[0], count[1]));
            } else if (i == 0 || s.charAt(i - 1) == '1') {
                count[0] = 1;
                count[1] = 0;
            } else {
                count[0]++;
            }
        }
        return res;
    }
}


【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年12月06日 0

暂无评论

推荐阅读
96AOqGW9dKgh