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

文章目录

Tag

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

题目来源

1. 最长平衡子字符串
   

解题思路

接下来会介绍两种方法，第一种方法很好理解，但是实现起来稍微复杂一点，时间复杂度也会高一点（

     O 
    
   
     ( 
    
    
    
      n 
     
    
      2 
     
    
   
     ) 
    
   
  
    O(n^2) 
   
  
O(n2)），方法二时间复杂度最优（ 
 
  
   
   
     O 
    
   
     ( 
    
   
     n 
    
   
     ) 
    
   
  
    O(n) 
   
  
O(n)），但是相对较难理解。

方法一：中心扩展

所有的

0

都在

1

的前面，符合要求的平衡字符串的中心是

01

，于是可以遍历字符串找到

01

，然后向两侧扩展寻找最长的平衡字符串。

实现代码

classSolution{public:intexpand(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;}intfindTheLongestBalancedSubstring(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;}};

复杂度分析

时间复杂度：

     O 
    
   
     ( 
    
    
    
      n 
     
    
      2 
     
    
   
     ) 
    
   
  
    O(n^2) 
   
  
O(n2)， 
 
  
   
   
     n 
    
   
  
    n 
   
  
n 为字符串 

s

的长度。

空间复杂度：

     O 
    
   
     ( 
    
   
     1 
    
   
     ) 
    
   
  
    O(1) 
   
  
O(1)。

方法二：计数

维护两个变量，

pre

表示上一段连续相同字符个数，

cur

表示当前连续的字符个数。我们遍历字符串

s

：

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

实现代码

classSolution{public:intfindTheLongestBalancedSubstring(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;}};

复杂度分析

时间复杂度：

     O 
    
   
     ( 
    
   
     n 
    
   
     ) 
    
   
  
    O(n) 
   
  
O(n)， 
 
  
   
   
     n 
    
   
  
    n 
   
  
n 为字符串 

s

的长度。

空间复杂度：

     O 
    
   
     ( 
    
   
     1 
    
   
     ) 
    
   
  
    O(1) 
   
  
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

写在最后

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

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

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