每日一题2609. 最长平衡子字符串

每日一题2609. 最长平衡子字符串

LeetCode题目：https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/

滑动窗口暴力解法

  直接构建n长度的字符串，使其符合000111的规律，然后滑动进行匹配。。

代码如下：

class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int result = 0;
        for (int i = 2; i <= s.length(); i+=2) {
            String check = "";
            for (int k = 0; k < i; k++) {
                if (k < i /2) {
                    check = check + '0';
                }else {
                    check = check + '1';
                }
            }
            for (int j = 0; j <= s.length() - i; j++) {
                String temp = s.substring(j, j + i);
                if (temp.equals(check)) {
                    result = i;
                }
            }
        }

        return result;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  因为每次都需要构建一个n长度的字符串，然后再进行逐个比较，因此十分暴力耗时间。

  因此，发现规律可以通过对0和1两个字符分别进行计数来进行计算，可以分为几种情况：

1、如果当前字符为0，则正常进行计数。

2、当前字符为1，则说明当前计数结束，由于字符串要根据0和1的最少数目来进行构建（“0000111”肯定是按照1的长度来构建，“001111”肯定以0的长度来计算），所以计算结果为min(result, 2 * min(count[0],count[1])).

3、当字符为0，且上一个字符为1的时候，说明当前计数的字符串已经不是平衡字符串了，因此清空前面的数据置零，并count[0]+1；

  因此代码如下：

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

        return result;
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20