# Leetcode 2609 Find the Longest Balanced Substring of a Binary String
###### tags: `Leetcode` `程式菜雞的coding日常`
## 題目原文

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.

## 題目理解
這題會給你一個只有0跟1的字串，找出其中最長的"balanced"子字串。
而balanced的定義為字串中所有0都在1前面且0與1的數量一樣。
## 解題思路
設兩個變數zero及one來記錄目前讀到的0與1的總數，然後根據不同情況做出對應的調整。
因為要符合balanced，所以0一定在1前面，換句話說，0會是一個balanced子字串的開頭，也就是說讀到0時若前面有讀到1則要清空1的數量並重新計算0的數量。

在遍歷字串的過程中只會有兩種情況:

1. 讀到0:
此時若1的數量非0，代表這個0的前一個字元是1，這個0會是新的子字串的開始，因此將one設為0，zero設為1；反之若1的數量為0，則zero++即可。
2. 讀到1:
此時代表已經進入balanced子字串的後半段了，首先one++，隨後就能根據當前的zero數量計算這個子字串的長度了，而此時的balanced子字串長度為`min(one,zero)*2`。
在這個情況下，每次找到合法的balanced子字串都要記錄其長度並在最後取最大值，或者是直接與當前最大值比較並記錄當前最大值就好。

## 程式實作

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int ans = 0, n = s.size(), zero = 0, one = 0;
        for (int i = 0 ; i < n; i++){
            if (s[i] == '0') {
                if (one) one = 0, zero = 1;
                else zero++;
            }
            else{
                one++;
                ans = max(ans, min(one, zero));
            }
        }
        return 2*ans;
    }
};

## 後記
第一次用hackmd做東西感覺很新奇(?
之後大概會更新leetcode的每日挑戰題目
~~(前提是我記得作而且我解的出來)~~
也會嘗試做weekly contest的題目，但hard我基本上是解不出來，所以就算了(?
搞不好之後我學一下LaTeX也能把數學筆記丟來這邊，好耶(?