A club runs a duty rota rota: a string whose letters are 'A', 'B', 'C' and 'D', one letter per day, naming the team on duty. The length of rota is a multiple of 4, and the rota is fair when every team is on duty for exactly len(rota) // 4 days.
To make the rota fair the secretary may pick one block of consecutive days and rewrite the teams on those days however she likes (days outside the block stay as they are). Return the length of the shortest block that makes the rota fair. Return 0 if the rota is already fair.
Examples
Input: rota = "ABCA"
Output: 1
Explanation: rewrite the last day as "D" to get "ABCD".
Input: rota = "AAAACDDB"
Output: 2
Explanation: each team needs 2 days. Rewriting days 2-3 ("AA") as "BC" gives "AABCCDDB".
Input: rota = "DCBA"
Output: 0
Constraints
4 <= len(rota) <= 10**5, andlen(rota)is a multiple of 4rotacontains only'A','B','C','D'- Target complexity: O(n). Trying every block (O(n²)) is too slow for the largest tests.
Goals
- Recast 'fix the inside' as a condition on what lies outside the window
- Shrink a window while it stays valid to find the shortest valid block