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.
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.
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://www.techieindoor.com/category/leetcode/
https://www.techieindoor.com/category/interview-questions/