Longest Substring with a and b count

Find the length of the longest substring containing equal numbers of 'a' and 'b' characters

Understand the Problem

Problem Statement

Given a string S containing only the characters 'a' and 'b', find and print the length L of the longest substring that contains an equal number of 'a' and 'b' characters.

Note: The algorithm must be optimized to execute within time limits for large inputs.

Constraints

1 ≤ Length of string S ≤ 100,000
String S contains only characters 'a' and 'b'
Time complexity should be O(n) or better
Space complexity should be O(n) or better

Examples

Example 1

Input

abaabba

Output

Explanation

The substring 'abaabb' (from index 0 to 5) has 3 'a's and 3 'b's, giving a length of 6. This is the longest such substring.

Example 2

Input

aaabaaabbbaaab

Output

Explanation

The substring 'aaabbbaa' (from index 2 to 9) has 4 'a's and 4 'b's, giving a length of 8. This is the longest such substring.

Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 100000
#define HASH_SIZE 200003  // Prime number for hash table

// Hash table structure
typedef struct {
    int key;
    int value;
    int occupied;
} HashEntry;

HashEntry hash_table[HASH_SIZE];

int hash(int key) {
    int h = abs(key) % HASH_SIZE;
    return h;
}

void insert_hash(int key, int value) {
    int index = hash(key);
    while (hash_table[index].occupied && hash_table[index].key != key) {
        index = (index + 1) % HASH_SIZE;
    }
    hash_table[index].key = key;
    hash_table[index].value = value;
    hash_table[index].occupied = 1;
}

int get_hash(int key) {
    int index = hash(key);
    while (hash_table[index].occupied) {
        if (hash_table[index].key == key) {
            return hash_table[index].value;
        }
        index = (index + 1) % HASH_SIZE;
    }
    return -2; // Not found indicator
}

int longestSubstring(char* str) {
    int n = strlen(str);
    int max_len = 0;
    int sum = 0;
    
    // Initialize hash table
    for (int i = 0; i < HASH_SIZE; i++) {
        hash_table[i].occupied = 0;
    }
    
    // Base case: sum 0 at index -1
    insert_hash(0, -1);
    
    for (int i = 0; i < n; i++) {
        if (str[i] == 'a') {
            sum += 1;
        } else {
            sum -= 1;
        }
        
        int prev_index = get_hash(sum);
        if (prev_index != -2) {
            max_len = (i - prev_index > max_len) ? (i - prev_index) : max_len;
        } else {
            insert_hash(sum, i);
        }
    }
    
    return max_len;
}

int main() {
    char str[MAX_LEN + 1];
    fgets(str, sizeof(str), stdin);
    
    // Remove newline if present
    int len = strlen(str);
    if (len > 0 && str[len - 1] == '\n') {
        str[len - 1] = '\0';
    }
    
    printf("%d\n", longestSubstring(str));
    return 0;
}

Time:O(n) - Single pass through the string with O(1) hash operations

Space:O(n) - Hash table stores at most n+1 different sums

Approach:

C Implementation:

1. Uses a hash table for O(1) average lookup time 2. Treats 'a' as +1 and 'b' as -1 3. Stores the first occurrence of each cumulative sum 4. When the same sum is encountered again, calculates the substring length 5. Returns the maximum length found Key Components: - Custom hash table implementation for O(1) operations - Handles hash collisions with linear probing - Uses modular arithmetic for hash function - Stores base case (sum=0 at index=-1) for substrings starting from index 0

Visual Explanation

Loading diagram...

All Problems