algoadvance

Leetcode 2609. Find the Longest Balanced Substring of a Binary String

Problem Statement

You are given a binary string s consisting only of the characters ‘0’ and ‘1’. A balanced binary string is defined as a binary string where the number of ‘0’s is equal to the number of ‘1’s. Your task is to find the length of the longest balanced substring in the given binary string.

Clarifying Questions

  1. Input Constraints: What is the maximum length of the binary string s? (Typical constraint might be around 10^5)
  2. Edge Cases: Can the input string be empty or contain only ‘0’s or ‘1’s?
  3. Output: Should we return the length of the longest balanced substring or the substring itself? (Usually, it is the length unless specified otherwise)

Strategy

To solve the problem efficiently:

  1. Prefix Sum Approach: We can use a prefix sum to keep track of the difference between the number of ‘0’s and ‘1’s up to the current index. This difference will help identify balanced substrings.
  2. Hash Map: Use a hash map to store the first occurrence of each prefix sum value. This way, if the same prefix sum appears again, the substring between these two indices is balanced.
  3. Iterate & Update: As we iterate through the binary string, we update the prefix sum and check its occurrence in the hash map to determine if a balanced substring exists.

Code

Here is the C++ implementation of the solution described above:

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>

int findLongestBalancedSubstring(const std::string& s) {
    std::unordered_map<int, int> prefixSumMap;
    int prefixSum = 0;
    int maxLength = 0;
    
    // Initialize the map with prefixSum value 0 at index -1 
    prefixSumMap[0] = -1;
    
    for (int i = 0; i < s.size(); ++i) {
        // Update the prefix sum
        if (s[i] == '0') {
            prefixSum++;
        } else {
            prefixSum--;
        }
        
        // Check if this prefix sum has been seen before
        if (prefixSumMap.find(prefixSum) != prefixSumMap.end()) {
            // Calculate the length of the balanced substring
            int length = i - prefixSumMap[prefixSum];
            maxLength = std::max(maxLength, length);
        } else {
            // Store the first occurrence of this prefix sum
            prefixSumMap[prefixSum] = i;
        }
    }
    
    return maxLength;
}

int main() {
    std::string s = "00110011";
    std::cout << "The length of the longest balanced substring is: " << findLongestBalancedSubstring(s) << std::endl;
    return 0;
}

Time Complexity

The time complexity of the solution is O(n), where n is the length of the string s. This is because we are iterating through the string once and performing constant time operations (hash map insertions and lookups) for each character. The space complexity is O(n) due to the hash map storing prefix sums and their respective indices.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI