Problem Link - Break the string
Problem Statement
A binary string is a sequence of 0's and 1's. We define the imbalance of a binary string to be the absolute difference between the number of 0’s in the string and the number of 1’s in the string. For instance, the imbalance of "0011011" is 1 and the imbalance of "101000" is 2.
Given a binary string of length N, we can partition it into segments, which are contiguous substrings of 0's and 1's. We are given an upper bound of K for the imbalance of a segment. Our goal is to partition the given string into the minimum number of segments such that no segment has an imbalace greater than K.
Formally, find the minimum number of partitions of the string into substrings such that each partition satisfies |cnt_0 - cnt_1| \leq K. cnt_0 and cnt_1 denotes the count of 0s and count of 1s respectively in the substring.
Approach
We start by iterating through the string, maintaining a running count of the imbalance between 0's and 1's. We also track the number of partitions we need. As we process each character, we keep adjusting this imbalance. If adding a character to the current segment causes the imbalance to exceed the given limit K, we create a new segment and reset the imbalance count for the new segment. This ensures that each segment we create has an imbalance that is within the allowed range. We continue this process until the entire string is processed, and the final count will give the minimum number of segments required.
Time Complexity
The time complexity is O(n), where n is the length of the binary string. This is because we only traverse the string once.
Space Complexity
The space complexity is O(n), as we store the binary string and the imbalance counts for each segment.