algoadvance

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

Problem Statement

You’re given a binary string s consisting only of characters ‘0’ and ‘1’. A balanced binary string is a 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 within s.

Clarifying Questions

  1. Can the input string be empty?
    • No, the input string will contain at least one character.
  2. Are there any constraints on the length of the input string?
    • Typical constraints would range up to 10^5 characters for efficient solutions.
  3. What should be returned if there’s no balanced substring?
    • If there’s no balanced substring, return 0.

Strategy

  1. Key Insight:
    • A balanced substring requires that the number of ‘0’s is equal to the number of ‘1’s over some continuous segment.
  2. Approach:
    • Use a hash map to keep track of the first occurrence of a particular count difference between ‘1’s and ‘0’s.
    • Traverse through the string while maintaining a count_difference which is updated as follows:
      • Increment for ‘1’
      • Decrement for ‘0’
    • If the same count difference appears again, it means the substring between the first occurrence and the current index has balanced ‘0’s and ‘1’s.
  3. Initialization:
    • Start by initializing the count_difference to 0 at position -1 to handle cases when the substring itself is balanced.
  4. Implementation:
    • Traverse through the string, compute the count_difference, and use the hash map to track and compute the lengths of potential balanced substrings.

Code

Here’s a Java implementation:

import java.util.HashMap;

public class LongestBalancedSubstring {
    public int findTheLongestBalancedSubstring(String s) {
        // HashMap to store the first occurrence of a count difference
        HashMap<Integer, Integer> map = new HashMap<>();
        // Initialize the map with count_difference 0 at position -1
        map.put(0, -1);
        
        int maxLength = 0;
        int countDifference = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // Update count difference
            countDifference += (s.charAt(i) == '1' ? 1 : -1);
            
            // If the count difference has been seen before
            if (map.containsKey(countDifference)) {
                // Calculate the length of balanced substring
                int length = i - map.get(countDifference);
                maxLength = Math.max(maxLength, length);
            } else {
                // Store the first occurrence of this count difference
                map.put(countDifference, i);
            }
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        LongestBalancedSubstring solution = new LongestBalancedSubstring();
        String binaryString = "110101100";
        System.out.println(solution.findTheLongestBalancedSubstring(binaryString)); // Output: 8
    }
}

Time Complexity

The time complexity for this approach is O(n) where n is the length of the input string s. This is because we traverse the string once, and both update and lookup operations in the hash map are O(1) on average.

Space Complexity

The space complexity is O(n) as well, since in the worst case, the hash map could store all the different count differences encountered during traversal.

This ensures that the solution is efficient and scalable for large input sizes.

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