Leetcode 2609: Find the Longest Balanced Substring of a Binary String
You are given a binary string consisting of only ‘0’s and ‘1’s. A substring of this binary string is considered balanced if it contains equal numbers of ‘0’s and ‘1’s, and all the ‘0’s come before the ‘1’s. Your task is to find the length of the longest balanced substring.
Problem
Approach
Steps
Complexity
Input: You are given a binary string s. The string consists only of '0's and '1's.
Example: s = "11010010"
Constraints:
• 1 <= s.length <= 50
• s consists only of '0' and '1'.
Output: Return the length of the longest balanced substring. A balanced substring is one where the count of '0's equals the count of '1's, and all '0's come before the '1's.
Example: Output: 4
Constraints:
• The output is a single integer representing the length of the longest balanced substring.
Goal: To find the longest balanced substring where the number of '0's equals the number of '1's and '0's come before '1's.
Steps:
• Initialize counters for '0's and '1's as you traverse the string.
• If a '0' is encountered, increase the '0' counter, and reset the '1' counter.
• If a '1' is encountered, check if it can balance the '0's in the substring. If so, update the answer with the longest balanced substring length found.
Goal: Ensure that the solution handles edge cases like empty substrings and different string lengths.
Steps:
• The input string length will be between 1 and 50.
Assumptions:
• The string contains only '0' and '1'.
• Input: s = "01000111"
• Explanation: In this case, the longest balanced substring is '000111' which has length 6. It contains 3 '0's followed by 3 '1's.
• Input: s = "00111"
• Explanation: The longest balanced substring is '0011', which has length 4, with 2 '0's followed by 2 '1's.
• Input: s = "111"
• Explanation: There is no balanced substring except for the empty one, so the output is 0.
Approach: We aim to find the longest balanced substring where the number of '0's equals the number of '1's, and the '0's come before the '1's.
Observations:
• The binary string contains only '0's and '1's, which makes it easier to check if a substring is balanced.
• A potential approach is to traverse the string while keeping track of the number of '0's and '1's. Each time the numbers are balanced, we check if the length of the current balanced substring is the longest found so far.
Steps:
• Initialize a counter for '0's and '1's while iterating through the string.
• When a '0' is found, increase the '0' counter and reset the '1' counter.
• When a '1' is found, check if it balances the '0's. If balanced, calculate the length of the balanced substring and update the answer.
Empty Inputs:
• An empty string should return 0 since there is no balanced substring.
Large Inputs:
• For larger input strings, ensure the solution runs efficiently within the constraints.
Special Values:
• Strings containing only '0's or only '1's should return 0 as they cannot form a balanced substring.
Constraints:
• Handle strings of length 1 properly and consider all possible substrings.
int findTheLongestBalancedSubstring(string s) {
int zr = 0, ans = 0;
int cnt[2] = {};
for(int i = 0; i < s.size(); i++) {
if(s[i] == '0') {
if(cnt[1]) {
cnt[0] = 0;
cnt[1] = 0;
}
cnt[0]++;
} else {
if(cnt[1] < cnt[0]) cnt[1]++;
else {
cnt[0] = 0;
cnt[1] = 0;
}
ans = max(cnt[1] * 2, ans);
}
}
return ans;
}
1 : Function
int findTheLongestBalancedSubstring(string s) {
The function begins by initializing two variables zr (zero count) and ans (the maximum balanced substring length).
2 : Variable Initialization
int zr = 0, ans = 0;
zr tracks the zeroes in the substring, while ans holds the maximum balanced substring length found.
3 : Array Initialization
int cnt[2] = {};
An array cnt[2] is used to track counts of '0's and '1's encountered in the substring.
4 : Loop
for(int i = 0; i < s.size(); i++) {
Iterates through the string 's' to process each character.
5 : Conditional
if(s[i] == '0') {
Checks if the current character is '0'.
6 : Inner Conditional
if(cnt[1]) {
If there are any '1's counted, reset the counts of both '0's and '1's.
7 : Reset Counts
cnt[0] = 0;
Reset count of '0's.
8 : Reset Counts
cnt[1] = 0;
Reset count of '1's.
9 : Increment Count
cnt[0]++;
Increment the count of '0's in the current substring.
10 : Else Conditional
} else {
If the current character is '1', execute the following logic.
11 : Conditional
if(cnt[1] < cnt[0]) cnt[1]++;
If there are fewer '1's than '0's, increment the count of '1's.
12 : Else Block
else {
If the count of '1's equals or exceeds '0's, reset the counts.
13 : Reset Counts
cnt[0] = 0;
Reset count of '0's.
14 : Reset Counts
cnt[1] = 0;
Reset count of '1's.
15 : Update Answer
ans = max(cnt[1] * 2, ans);
Update the maximum balanced substring length by comparing the current balanced substring's length (2 * cnt[1]) with ans.
16 : Return Statement
return ans;
Return the maximum balanced substring length.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear in the size of the string, as the algorithm iterates over the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, as only a few variables are used to track the balanced substring length.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus