【每日一题】最长平衡子字符串

Tag

【计数】【中心扩展】【字符串】

---

题目来源

2609. 最长平衡子字符串

---

解题思路

接下来会介绍两种方法，第一种方法很好理解，但是实现起来稍微复杂一点，时间复杂度也会高一点（$O(n^2)$），方法二时间复杂度最优（$O(n)$），但是相对较难理解。

方法一：中心扩展

所有的 0 都在 1 的前面，符合要求的平衡字符串的中心是 01，于是可以遍历字符串找到 01，然后向两侧扩展寻找最长的平衡字符串。

实现代码

class Solution {
public:
    int expand(string s, int x, int y) {
        int n = s.size();
        int res = 0;
        while (x >= 0 && y <= n-1 && s[x] == '0' &&s[y] == '1') {
            --x;
            ++y;
        }
        return y - x - 1;
    }
    int findTheLongestBalancedSubstring(string s) {
        int n = s.size();
        int res = 0;
        for (int i = 0; i < n-1; ++i) {
            if (s[i] == '0' && s[i+1] == '1') {
                res = max(res, expand(s, i, i+1));
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

时间复杂度：$O(n^2)$，$n$ 为字符串 s 的长度。

空间复杂度：$O(1)$。

方法二：计数

维护两个变量，pre 表示上一段连续相同字符个数，cur 表示当前连续的字符个数。我们遍历字符串 s：

• 更新 cur；
• 如果当前字符到达字符串尾或者连续字符结束了：
  • 如果当前连续字符是 '1'，那么更新最长平衡子字符串长度 res；
• 更新 pre = curr，cur = 0，为接下来的遍历做准备。
• 最后返回 res。

实现代码

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int res = 0;
        int pre = 0, cur = 0;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            cur++;
            if (i == n - 1 || s[i] != s[i + 1]) { 
                if (s[i] == '1') {
                    res = max(res, min(pre, cur) * 2);
                }
                pre = cur;
                cur = 0;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析

时间复杂度：$O(n)$，$n$ 为字符串 s 的长度。

空间复杂度：$O(1)$。

---

其他语言

python3

只给出最优的方法即方法二的 python3 语言代码。

class Solution:
    def findTheLongestBalancedSubstring(self, s: str) -> int:
        res = pre = cur = 0
        for i, c in enumerate(s):
            cur += 1
            if i == len(s) - 1 or c != s[i + 1]:  # i 是连续相同段的末尾
                if c == '1':
                    ans = max(ans, min(pre, cur) * 2)
                pre = cur
                cur = 0
        return res
1
2
3
4
5
6
7
8
9
10
11

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。