2609. Find the Longest Balanced Substring of a Binary String

Approach 1: whiles inside for

• Time: $O(n)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  int findTheLongestBalancedSubstring(string s) {
    int ans = 0;

    for (int i = 0; i < s.length();) {
      int zeros = 0;
      int ones = 0;
      while (i < s.length() && s[i] == '0') {
        ++zeros;
        ++i;
      }
      while (i < s.length() && s[i] == '1') {
        ++ones;
        ++i;
      }
      ans = max(ans, min(zeros, ones));
    }

    return ans * 2;
  }
};

class Solution {
  public int findTheLongestBalancedSubstring(String s) {
    int ans = 0;

    for (int i = 0; i < s.length();) {
      int zeros = 0;
      int ones = 0;
      while (i < s.length() && s.charAt(i) == '0') {
        ++zeros;
        ++i;
      }
      while (i < s.length() && s.charAt(i) == '1') {
        ++ones;
        ++i;
      }
      ans = Math.max(ans, Math.min(zeros, ones));
    }

    return ans * 2;
  }
}

class Solution:
  def findTheLongestBalancedSubstring(self, s: str) -> int:
    ans = 0

    i = 0
    while i < len(s):
      zeros = 0
      ones = 0
      while i < len(s) and s[i] == '0':
        zeros += 1
        i += 1
      while i < len(s) and s[i] == '1':
        ones += 1
        i += 1
      ans = max(ans, min(zeros, ones))

    return ans * 2

Approach 2: Single for

• Time: $O(n)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  int findTheLongestBalancedSubstring(string s) {
    int ans = 0;
    int count0 = 0;
    int count1 = 0;

    for (const char c : s) {
      if (c == '0') {
        count0 = count1 > 0 ? 1 : count0 + 1;
        count1 = 0;
      } else {  // c == '1'
        ++count1;
      }
      if (count0 >= count1)
        ans = max(ans, count1);
    }

    return ans * 2;
  }
};

class Solution {
  public int findTheLongestBalancedSubstring(String s) {
    int ans = 0;
    int zeros = 0;
    int ones = 0;

    for (final char c : s.toCharArray()) {
      if (c == '0') {
        zeros = ones > 0 ? 1 : zeros + 1;
        ones = 0;
      } else { // c == '1'
        ++ones;
      }
      if (zeros >= ones)
        ans = Math.max(ans, ones);
    }

    return ans * 2;
  }
}

class Solution:
  def findTheLongestBalancedSubstring(self, s: str) -> int:
    ans = 0
    zeros = 0
    ones = 0

    for c in s:
      if c == '0':
        zeros = 1 if ones > 0 else zeros + 1
        ones = 0
      else:  # c == '1'
        ones += 1
      if zeros >= ones:
        ans = max(ans, ones)

    return ans * 2