Balanced Substring Checker

January 14, 2024

Problem #

Given a string s consisting of only two characters A and B, find the length of the longest substring that contains an equal number of As and Bs.

Example: #

Input: s = "ABABBAABB" Output: 8 (The longest balanced substring is “ABABBAAB”)

Solution Approach: #

The solution involves using a hash map to keep track of the counts of As and Bs and their differences at each index. The idea is to find two indices i and j where the difference in the count of As and Bs is the same, indicating that the substring between i and j is balanced.

Algorithm Steps: #

1. Initialize a hash map to store the difference between the count of As and Bs at each index.
2. Initialize variables to keep track of the maximum length of a balanced substring.
3. Iterate through the string, updating the counts of As and Bs.
4. For each index, calculate the difference between the counts of A and B.
5. Check if this difference has been seen before in the hash map. If yes, update the maximum length of the balanced substring.
6. If the difference is new, store it in the hash map with the current index.
7. Return the maximum length found.

Code: #

def longestBalancedSubstring(s):
    count_map = {0: -1}
    max_length = 0
    count_A, count_B = 0, 0

    for i in range(len(s)):
        if s[i] == 'A':
            count_A += 1
        else:
            count_B += 1

        diff = count_A - count_B

        if diff in count_map:
            max_length = max(max_length, i - count_map[diff])
        else:
            count_map[diff] = i

    return max_length

# Example usage
print(longestBalancedSubstring("ABABBAABB"))  # Output: 8

Time Complexity: #

The time complexity is O(N), where N is the length of the string s. This is because the algorithm iterates through the string once.

Space Complexity: #

The space complexity is O(N) in the worst case, due to the hash map storing the differences at each index.