Given a string, find the smallest length of a substring that can be repeated to form the whole string after rearranging characters within each block.
Problem
You are given a string s. Determine the minimum length L such that the string can be partitioned into contiguous blocks of length L, and each block can be rearranged to match the same multiset of characters as every other block.
In other words, after splitting s into equal-sized pieces, every piece should be an anagram of the others. Return the smallest such block length.
If no such partition exists, return the length of the whole string.
Input Format
- A single string
s. scontains only lowercase English letters.
Output Format
- Return an integer: the minimum valid block length.
Constraints
sconsists of lowercase English letters only.
Example 1
Input
s = "abbaabba"
Output
4
Explanation
The string can be split into ["abba", "abba"]. Both blocks have the same character counts, so the minimum valid length is 4.
Example 2
Input
s = "abcabcabc"
Output
3
Explanation
Split into ["abc", "abc", "abc"]. Each block is an anagram of the others, so the minimum valid length is 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.