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.
Constraints:
1 <= s.length <= 50'0' <= s[i] <= '1'program main
implicit none
character(len=50) :: s
integer :: i, j, n, m, max_len
! Examples
s = "01000111"
write(*,*) "Example 1:"
write(*,*) "Input:", s
write(*,*) "Output:", longest_balanced_substring(s)
write(*,*) ""
s = "00111"
write(*,*) "Example 2:"
write(*,*) "Input:", s
write(*,*) "Output:", longest_balanced_substring(s)
write(*,*) ""
s = "111"
write(*,*) "Example 3:"
write(*,*) "Input:", s
write(*,*) "Output:", longest_balanced_substring(s)
write(*,*) ""
contains
function longest_balanced_substring(s) result(max_len)
implicit none
character(len=*), intent(in) :: s
integer :: i, j, n, m, max_len
max_len = 0
do i = 1, len(s) - 1
do j = i + 1, len(s)
if (is_balanced(s(i:j))) then
max_len = max(max_len, j - i + 1)
end if
end do
end do
end function longest_balanced_substring
function is_balanced(s) result(res)
implicit none
character(len=*), intent(in) :: s
logical :: res
res = .true.
do i = 1, len(s)
if (s(i:i) == "0") then
if (any(s(i+1:) /= "0")) then
res = .false.
exit
end if
else if (s(i:i) == "1") then
if (any(s(i-1:) /= "1")) then
res = .false.
exit
end if
end if
end do
end function is_balanced
end program maintemp.f95:51:24:
51 | if (any(s(i+1:) /= "0")) then
| 1
Error: ‘mask’ argument of ‘any’ intrinsic at (1) must be a logical array
temp.f95:56:24:
56 | if (any(s(i-1:) /= "1")) then
| 1
Error: ‘mask’ argument of ‘any’ intrinsic at (1) must be a logical array
program longest_balanced_substring
implicit none
integer :: i, j, k, n, m, max_len
character(len=50) :: s
! Read input
read(*,*) s
! Initialize variables
n = len_trim(s)
m = 0
max_len = 0
! Iterate over the string
do i = 1, n
! Check if the current character is a zero
if (s(i:i) == '0') then
! Increment the number of zeroes
m = m + 1
! Check if the current character is a one
else if (s(i:i) == '1') then
! Decrement the number of zeroes
m = m - 1
end if
! Check if the current substring is balanced
if (m >= 0) then
! Update the maximum length of the balanced substring
max_len = max(max_len, m)
end if
end do
! Print output
write(*,*) max_len
end program longest_balanced_substring
At line 8 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7d6139239960 in ??? #1 0x7d613923a4d9 in ??? #2 0x7d613948e17b in ??? #3 0x7d6139487684 in ??? #4 0x7d61394882aa in ??? #5 0x56e2d6915219 in MAIN__ #6 0x56e2d6915343 in main
def longestBalancedSubstring(s):
max_len = 0
zeros = ones = 0
for c in s:
if c == '0':
zeros += 1
else:
ones += 1
if zeros == ones:
max_len = max(max_len, zeros * 2)
elif zeros > ones:
zeros = ones = 0
zeros = ones = 0
for c in reversed(s):
if c == '0':
zeros += 1
else:
ones += 1
if zeros == ones:
max_len = max(max_len, zeros * 2)
elif zeros < ones:
zeros = ones = 0
return max_len
The algorithm scans the string s twice. In the first pass, it counts the number of zeros and ones.
1. Whenever the count of zeros and ones is the same, the maximum length of the balanced substring should be updated by selecting the maximum value between max_len and zeros * 2.
2. If the count of zeros is greater than the count of ones, the current possibility of a balanced substring has failed, so zeros and ones are reset to 0.
In the second pass, the process is almost the same, but this time it iterates from the end of the string to the beginning. When the count of ones is greater than the count of zeros, zeros and ones are reset to 0.
After the two passes, the variable max_len stores the length of the longest balanced substring in the input string s.
int longestBalancedSubstring(string s) {
int max_len = 0;
int zeros = 0;
int ones = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '0') {
zeros++;
} else {
ones++;
}
if (zeros == ones) {
max_len = max(max_len, zeros * 2);
} else if (zeros > ones) {
zeros = ones = 0;
}
}
zeros = ones = 0;
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] == '0') {
zeros++;
} else {
ones++;
}
if (zeros == ones) {
max_len = max(max_len, zeros * 2);
} else if (zeros < ones) {
zeros = ones = 0;
}
}
return max_len;
}
The algorithm scans the string s twice. In the first pass, it counts the number of zeros and ones.
1. Whenever the count of zeros and ones is the same, the maximum length of the balanced substring should be updated by selecting the maximum value between max_len and zeros * 2.
2. If the count of zeros is greater than the count of ones, the current possibility of a balanced substring has failed, so zeros and ones are reset to 0.
In the second pass, the process is almost the same, but this time it iterates from the end of the string to the beginning. When the count of ones is greater than the count of zeros, zeros and ones are reset to 0.
After the two passes, the variable max_len stores the length of the longest balanced substring in the input string s.