Find max equal-frequency block count for each prefix
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string `S` of length `n` (e.g., uppercase letters), for every prefix `P = S[0..i]` (for `i = 0..n-1`), compute the **maximum** integer `k` such that:
- The prefix length `|P|` is divisible by `k`.
- `P` can be partitioned into `k` **contiguous** blocks of equal length `L = |P|/k`.
- For every character `c`, the number of occurrences of `c` is the **same in every block**.
Equivalently, all `k` blocks must have identical character-frequency vectors (so each block is an anagram of the others).
**Task:** Output an array `ans[1..n]` where `ans[i]` is the maximum `k` for the prefix of length `i`.
#### Input
- A string `S`
#### Output
- `n` integers, where the `i`-th integer is the answer for prefix `S[0..i-1]`.
#### Example
`S = "ABBA"`
- Prefix `"A"` → `k=1`
- Prefix `"AB"` → cannot split into 2 equal-frequency blocks (`"A"` vs `"B"`), so `k=1`
- Prefix `"ABB"` → `k=1`
- Prefix `"ABBA"` → split into `"AB" | "BA"`, both have `{A:1,B:1}`, so `k=2`
Output: `1 1 1 2`.
Quick Answer: This question evaluates proficiency in string processing, frequency-vector reasoning, and prefix-based partitioning to determine equal-frequency contiguous blocks.
Given a string S consisting of uppercase English letters, compute an answer for every prefix of S.
For a prefix P of length m, find the maximum integer k such that:
- m is divisible by k,
- P can be split into k contiguous blocks of equal length L = m / k,
- every block has the same character-frequency vector.
In other words, all k blocks must be anagrams of one another.
Return an array ans of length n where ans[i - 1] is the maximum k for the prefix S[0:i]. If S is empty, return an empty array.
Example:
- S = "ABBA"
- Prefix "A" -> 1
- Prefix "AB" -> 1
- Prefix "ABB" -> 1
- Prefix "ABBA" -> 2 because "AB" and "BA" have the same frequencies
Return [1, 1, 1, 2].
Constraints
- 0 <= len(S) <= 100000
- S consists only of uppercase English letters 'A' to 'Z'
Examples
Input: "ABBA"
Expected Output: [1, 1, 1, 2]
Explanation: Only the full prefix of length 4 can be split into more than one valid block: "AB" | "BA", both with frequencies {A:1, B:1}.
Input: "AAAA"
Expected Output: [1, 2, 3, 4]
Explanation: Every prefix of length i can be split into i single-character blocks, and all blocks have the same frequency vector.
Input: "AABB"
Expected Output: [1, 2, 1, 1]
Explanation: Prefix "AA" can be split into "A" | "A". But "AABB" cannot be split into 2 or 4 equal-frequency blocks.
Input: "ABABAB"
Expected Output: [1, 1, 1, 2, 1, 3]
Explanation: Length 4 works as "AB" | "AB", and length 6 works as "AB" | "AB" | "AB".
Input: ""
Expected Output: []
Explanation: An empty string has no prefixes, so the answer is an empty list.
Hints
- Instead of fixing a prefix and trying all divisors, fix a block length L. Then a prefix of length q * L is valid exactly when its first q blocks of size L all have the same frequency vector.
- Use prefix frequency counts for the 26 letters so you can compare any two blocks in O(26), which is O(1) for a fixed alphabet.