EasyNo. 2609
Find the Longest Balanced Substring of a Binary String — LeetCode 2609 Python Solution
- Pattern
- Hash Map
- Topics
- String
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- s = "01000111"
- Output
- 6
- Explanation
- The longest balanced substring is "000111", which has length 6.
Python solution
class Solution:
def findTheLongestBalancedSubstring(self, s: str) -> int:
def check(i, j):
cnt = 0
for k in range(i, j + 1):
if s[k] == '1':
cnt += 1
elif cnt:
return False
return cnt * 2 == (j - i + 1)
n = len(s)
ans = 0
for i in range(n):
for j in range(i + 1, n):
if check(i, j):
ans = max(ans, j - i + 1)
return ansComplexity
- Time
- O(n3)
- Space · auxiliary
- O(1)
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2609. Find the Longest Balanced Substring of a Binary String is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0006 | Zigzag Conversion | Medium |
| 0008 | String to Integer (atoi) | Medium |
| 0038 | Count and Say | Medium |
| 0058 | Length of Last Word | Easy |
| 0065 | Valid Number | Hard |
| 0068 | Text Justification | Hard |
Frequently asked questions
- How hard is LeetCode 2609. Find the Longest Balanced Substring of a Binary String?
LeetCode 2609. Find the Longest Balanced Substring of a Binary String is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2609. Find the Longest Balanced Substring of a Binary String?
The Python solution on this page runs in O(n3).
- What is the space complexity of LeetCode 2609. Find the Longest Balanced Substring of a Binary String?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2609. Find the Longest Balanced Substring of a Binary String cover?
LeetCode 2609. Find the Longest Balanced Substring of a Binary String is tagged String on LeetCode.