Find max equal-frequency block count for each prefix

Problem Statement

Given a string s, we define a 'balanced prefix' of length k (where 1 <= k <= len(s)) as a prefix that can be partitioned into one or more contiguous blocks such that every block contains the exact same number of distinct characters, and each distinct character within a block appears with the same frequency.

For example, if a block has two distinct characters 'a' and 'b' each appearing 2 times, the block 'aabb' is balanced. A prefix is balanced if it is the concatenation of one or more such blocks.

Implement a function count_balanced_prefixes(s) that returns a list of integers where the i-th element is the maximum number of balanced blocks the prefix s[0...i] can be divided into. If a prefix cannot be partitioned into such blocks, return 0 for that position.

Function Signature

def count_balanced_prefixes(s: str) -> List[int]:

Constraints

• 1 <= len(s) <= 2000
• s consists of lowercase English letters.

Examples

Example 1: Input: s = "aabbcc" Output: [0, 0, 1, 0, 0, 3] Explanation:

• "aa" (1 block: 'a':2), "aabb" (1 block: 'a':2, 'b':2), "aabbcc" (3 blocks: 'a':2, 'b':2, 'c':2).

Example 2: Input: s = "abc" Output: [0, 0, 1] Explanation:

• "abc" (1 block: 'a':1, 'b':1, 'c':1).

Edge Cases

• Single character strings (always 1 block if valid).
• Strings with all identical characters.
• Prefixes that cannot be partitioned.