Menu Close

Leetcode 2609: Find the Longest Balanced Substring of a Binary String Solution

Here, we will see Find the Longest Balanced Substring of a Binary String Solution of leet code 2609 problem.

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.

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.

Approach:

  • Iterate through each characters of string
    • If character starts with ‘0’ then count all zeros
    • Then count all ‘1’ ones
    • Break the loop when next zero comes up.
    • Get the minimum number between number of zero’s and one’s
    • Update the max variables

Find the Longest Balanced Substring of a Binary String Solution in C++:

Here, we will be solving problem in multiple ways with code.

C++ code 1:

class Solution {

public:

    int findTheLongestBalancedSubstring(string s) {

        bool is_found = false;

        int max = 0;

        
        if(s.length() == 0) {

            return 0;

        }

        
        for(int i = 0; i < s.length(); i++) {

            if(s[i] == '0') {

                int zero = 0, one = 0;
                
                while(i < s.length() && s[i] == '0') i++, zero++;

                while(i < s.length() && s[i] == '1') i++, one++;

                
                i--;

                
                int len = min(zero, one);

                if(max < (len * 2)) {

                    max = len * 2;

                }

            }

        }

        return max;

    }

};

C++ code 2:

class Solution {

public:

    int findTheLongestBalancedSubstring(string str) {
        
        int cnt1=0,cnt2=0,ans=0;
        
        for(auto x:str)
        {
            if(x=='1')
            {
                cnt1++;
            }
            else
            {
                if(cnt1==0)
                {
                    cnt2++;
                    continue;
                }
                
                ans=max(ans,min(cnt1,cnt2)*2);
                cnt1=0;
                cnt2=1;
            }
        }
        
        ans=max(ans,min(cnt1,cnt2)*2);
        
        return ans;
    }
};

Output:

Input: s = "01000111"
Output: 6

Time complexity: O(n)

Space complexity: O(1)

To check more leetcode problem’s solution. Pls click given below link:

https://techieindoor.com/category/leetcode/

https://techieindoor.com/category/interview-questions/

https://leetcode.com/

Posted in C++, Easy, Leetcode

Leave a Reply

Your email address will not be published. Required fields are marked *