Count Balanced Substrings

Given a string s consisting only of the characters 'a' and 'b', partition the string into the minimum number of non‐empty substrings such that each substring contains an equal number of 'a' and 'b'.

You are required to use a greedy algorithm: iterate over the string and maintain separate counts for 'a' and 'b'. Every time these counts become equal (and nonzero), you have found a balanced substring. Reset the counts and continue until the end of the string.

The answer is the number of balanced substrings you can obtain in this way.

Formally, if you denote the counts of 'a' and 'b' in a substring T by \(a(T)\) and \(b(T)\) respectively, then for each substring, \(a(T) = b(T)\). The goal is to minimize the number of substrings, which corresponds exactly to counting each occurrence of equality as you scan through the string.

Note: If it is not possible to partition the string in a way such that every part is balanced, then the answer is 0.

inputFormat

The input consists of a single line containing a string s of arbitrary length, composed exclusively of the characters 'a' and 'b'.

outputFormat

Output a single integer — the minimum number of substrings into which the string can be partitioned such that each substring contains an equal number of 'a' and 'b'.

aabbaabb

2