Welcome to Subscribe On Youtube

2609. Find the Longest Balanced Substring of a Binary String

Description

You are given a binary string s consisting only of zeroes and ones.

A substring of s is considered balanced if all zeroes are before ones and the number of zeroes is equal to the number of ones inside the substring. Notice that the empty substring is considered a balanced substring.

Return the length of the longest balanced substring of s.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: s = "01000111"
Output: 6
Explanation: The longest balanced substring is "000111", which has length 6.

Example 2:

Input: s = "00111"
Output: 4
Explanation: The longest balanced substring is "0011", which has length 4. 

Example 3:

Input: s = "111"
Output: 0
Explanation: There is no balanced substring except the empty substring, so the answer is 0.

 

Constraints:

• 1 <= s.length <= 50
• '0' <= s[i] <= '1'

Solutions

Solution 1: Brute force

Since the range of $n$ is small, we can enumerate all substrings $s[i..j]$ to check if it is a balanced string. If so, update the answer.

The time complexity is $O(n^3)$, and the space complexity is $O(1)$. Where $n$ is the length of string $s$.

Solution 2: Enumeration optimization

We use variables $zero$ and $one$ to record the number of continuous $0$ and $1$.

Traverse the string $s$, for the current character $c$:

• If the current character is '0', we check if $one$ is greater than $0$, if so, we reset $zero$ and $one$ to $0$, and then add $1$ to $zero$.
• If the current character is '1', we add $1$ to $one$, and update the answer to $ans = max(ans, 2 \times min(one, zero))$.

After the traversal is complete, we can get the length of the longest balanced substring.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Where $n$ is the length of string $s$.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• 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;
      }
  };
  

• 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
  
  

• 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
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

• 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
      }
  }
  

All Problems

All Solutions