题目重点：用总字符频次的GCD筛候选块数，再以精确前缀频次向量核对，避免把必要条件当充分条件。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 对每个非空前缀返回最大块数k；每块连续且同长度，各字符计数完全相同，不要求字符排列相同。
- 同频不是只有相同字符集合；区分大小写，示例允许任意Python code point。
- 空串返回空结果。题目没有复杂度门槛、编码或正式输出schema；最大块数口径明确为训练解释。
解题路线
- 前缀长度i、总计数C_c若分k块，每块字符c计数必须C_c/k，因此k整除全部C_c，候选是gcd(C_c)的约数；所有计数和为i也保证k整除i。
- GCD仅是必要条件。例如AABB总计数gcd=2，但两块AA和BB频率不同，最大只能1；不能直接输出GCD。
- 保存字符计数前缀向量P[t]。长度d=i/k的块[j*d,(j+1)*d)频次为P[(j+1)*d]-P[j*d]，与第一块精确比较；降序候选首次通过就是最大k。
- 本文比较完整计数向量而非hash，仅在候选检查完全满足时接受。普通rolling hash比较字符顺序，不等价于histogram；向量hash也有碰撞风险，需要多hash或最终精确核验。
- 实现用isqrt枚举约数，含互补约数并去重；gcd对0计数自然忽略，但非空前缀的g>0。跨前缀频次变化时重新检查，不能假定前一答案单调。
- 性能追问可讨论固定字母表、短路检查和减少候选，但不能把每块向量验证写成O(1)后隐去字符维度和块数。若正式输入很大，需再找额外结构与确认性能门槛。
手动走一遍
训练ABBA各前缀输出[1,1,1,2]，最后AB与BA同频；AABB最后只能1，虽总A/B各2却AA/BB不同。AAAA输出[1,2,3,4]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from math import gcd,isqrt
def maximum_blocks_per_prefix(text):
"""For each nonempty prefix, maximum equal-length blocks with equal histograms."""
alphabet={ch:i for i,ch in enumerate(sorted(set(text)))}
width=len(alphabet)
prefix=[[0]*width]
for ch in text:
row=prefix[-1].copy()
row[alphabet[ch]]+=1
prefix.append(row)
answer=[]
for length in range(1,len(text)+1):
common=0
for count in prefix[length]:common=gcd(common,count)
candidates=set()
for divisor in range(1,isqrt(common)+1):
if common%divisor==0:
candidates.update((divisor,common//divisor))
for blocks in sorted(candidates,reverse=True):
block_size=length//blocks
if all(all(prefix[right][a]-prefix[right-block_size][a]==prefix[block_size][a]
for a in range(width))
for right in range(2*block_size,length+1,block_size)):
answer.append(blocks)
break
return answer
复杂度
字母维度u、长度n，前缀存储O(nu)。每前缀枚举约数O(√g_i)，验证最坏O(u·Σ_{k|g_i}k)；全程可用宽松上界O(u·n² log n)，不能把该训练基线声称线性。
易错点与追问
容易失分的边界
- 直接把GCD当答案。
- 比较子串顺序而非字符频次。
- 只比字符集合。
- 单hash碰撞却称完全精确。
继续深挖
- 仅26字母可怎样减少常数？
- 返回所有可行k而不是最大k？
- 超长输入对性能门槛有哪些澄清问题？
