Question

2609. 最长平衡子字符串

English Version

题目描述

给你一个仅由 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'

解法

方法一：暴力枚举

注意到数据范围很小，因此，我们可以枚举所有的子串 $s[i..j]$，检查其是否为平衡子串，如果是，则更新答案。

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

class Solution:
  def findTheLongestBalancedSubstring(self, s: str) -> int:
    def check(i, j):
      cnt = 0
      for k in range(i, j + 1):
        if s[k] == '1':
          cnt += 1
        elif cnt:
          return False
      return cnt * 2 == (j - i + 1)

    n = len(s)
    ans = 0
    for i in range(n):
      for j in range(i + 1, n):
        if check(i, j):
          ans = max(ans, j - i + 1)
    return ans

class Solution {
  public int findTheLongestBalancedSubstring(String s) {
    int n = s.length();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (check(s, i, j)) {
          ans = Math.max(ans, j - i + 1);
        }
      }
    }
    return ans;
  }

  private boolean check(String s, int i, int j) {
    int cnt = 0;
    for (int k = i; k <= j; ++k) {
      if (s.charAt(k) == '1') {
        ++cnt;
      } else if (cnt > 0) {
        return false;
      }
    }
    return cnt * 2 == j - i + 1;
  }
}

class Solution {
public:
  int findTheLongestBalancedSubstring(string s) {
    int n = s.size();
    int ans = 0;
    auto check = [&](int i, int j) -> bool {
      int cnt = 0;
      for (int k = i; k <= j; ++k) {
        if (s[k] == '1') {
          ++cnt;
        } else if (cnt) {
          return false;
        }
      }
      return cnt * 2 == j - i + 1;
    };
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (check(i, j)) {
          ans = max(ans, j - i + 1);
        }
      }
    }
    return ans;
  }
};

func findTheLongestBalancedSubstring(s string) (ans int) {
  n := len(s)
  check := func(i, j int) bool {
    cnt := 0
    for k := i; k <= j; k++ {
      if s[k] == '1' {
        cnt++
      } else if cnt > 0 {
        return false
      }
    }
    return cnt*2 == j-i+1
  }
  for i := 0; i < n; i++ {
    for j := i + 1; j < n; j++ {
      if check(i, j) {
        ans = max(ans, j-i+1)
      }
    }
  }
  return
}

function findTheLongestBalancedSubstring(s: string): number {
  const n = s.length;
  let ans = 0;
  const check = (i: number, j: number): boolean => {
    let cnt = 0;
    for (let k = i; k <= j; ++k) {
      if (s[k] === '1') {
        ++cnt;
      } else if (cnt > 0) {
        return false;
      }
    }
    return cnt * 2 === j - i + 1;
  };
  for (let i = 0; i < n; ++i) {
    for (let j = i + 1; j < n; j += 2) {
      if (check(i, j)) {
        ans = Math.max(ans, j - i + 1);
      }
    }
  }
  return ans;
}

impl Solution {
  pub fn find_the_longest_balanced_substring(s: String) -> i32 {
    let check = |i: usize, j: usize| -> bool {
      let mut cnt = 0;

      for k in i..=j {
        if s.as_bytes()[k] == b'1' {
          cnt += 1;
        } else if cnt > 0 {
          return false;
        }
      }

      cnt * 2 == j - i + 1
    };

    let mut ans = 0;
    let n = s.len();
    for i in 0..n - 1 {
      for j in (i + 1..n).rev() {
        if j - i + 1 < ans {
          break;
        }

        if check(i, j) {
          ans = std::cmp::max(ans, j - i + 1);
          break;
        }
      }
    }

    ans as i32
  }
}

方法二：枚举优化

我们用变量 $zero$ 和 $one$ 分别记录当前连续的 $0$ 和 $1$ 的个数。

遍历字符串 $s$，对于当前字符 $c$：

• 如果当前字符为 '0'，我们判断此时 $one$ 是否大于 $0$，是则将 $zero$ 和 $one$ 重置为 $0$，接下来将 $zero$ 加 $1$。
• 如果当前字符为 '1'，则将 $one$ 加 $1$，并更新答案为 $ans = \max(ans, 2 \times \min(one, zero))$。

遍历结束后，即可得到最长的平衡子串的长度。

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

class Solution:
  def findTheLongestBalancedSubstring(self, s: str) -> int:
    ans = zero = one = 0
    for c in s:
      if c == '0':
        if one:
          zero = one = 0
        zero += 1
      else:
        one += 1
        ans = max(ans, 2 * min(one, zero))
    return ans

class Solution {
  public int findTheLongestBalancedSubstring(String s) {
    int zero = 0, one = 0;
    int ans = 0, n = s.length();
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '0') {
        if (one > 0) {
          zero = 0;
          one = 0;
        }
        ++zero;
      } else {
        ans = Math.max(ans, 2 * Math.min(zero, ++one));
      }
    }
    return ans;
  }
}

class Solution {
public:
  int findTheLongestBalancedSubstring(string s) {
    int zero = 0, one = 0;
    int ans = 0;
    for (char& c : s) {
      if (c == '0') {
        if (one > 0) {
          zero = 0;
          one = 0;
        }
        ++zero;
      } else {
        ans = max(ans, 2 * min(zero, ++one));
      }
    }
    return ans;
  }
};

func findTheLongestBalancedSubstring(s string) (ans int) {
  zero, one := 0, 0
  for _, c := range s {
    if c == '0' {
      if one > 0 {
        zero, one = 0, 0
      }
      zero++
    } else {
      one++
      ans = max(ans, 2*min(zero, one))
    }
  }
  return
}

function findTheLongestBalancedSubstring(s: string): number {
  let zero = 0;
  let one = 0;
  let ans = 0;
  for (const c of s) {
    if (c === '0') {
      if (one > 0) {
        zero = 0;
        one = 0;
      }
      ++zero;
    } else {
      ans = Math.max(ans, 2 * Math.min(zero, ++one));
    }
  }
  return ans;
}

impl Solution {
  pub fn find_the_longest_balanced_substring(s: String) -> i32 {
    let mut zero = 0;
    let mut one = 0;
    let mut ans = 0;

    for &c in s.as_bytes().iter() {
      if c == b'0' {
        if one > 0 {
          zero = 0;
          one = 0;
        }
        zero += 1;
      } else {
        one += 1;
        ans = std::cmp::max(ans, std::cmp::min(zero, one) * 2);
      }
    }

    ans
  }
}