Alternating Strings (APCS 2017-10 Intermediate)

A string consisting entirely of uppercase English letters is called an uppercase string. A string consisting entirely of lowercase English letters is called a lowercase string.

Given a positive integer \(k\), a string is called a \(k\)-alternating string if it is formed by alternately concatenating uppercase and lowercase strings, each of length exactly \(k\). The first block may have either case, and a single block is also valid.

For example, StRiNg is a \(1\)-alternating string, and heLLow is a \(2\)-alternating string. For \(k=2\) and input string aBBaaa, the longest contiguous \(k\)-alternating substring is BBaa, whose length is \(4\).

Find the longest contiguous substring of the given string that is a \(k\)-alternating string.

Input Format

The first line contains an integer \(k\).

The second line contains a nonempty string \(s\) consisting only of English letters A–Z and a–z, with no spaces.

Constraints

• \(1 \le k \le 100000\)
• \(1 \le |s| \le 100000\)
• \(s\) contains only uppercase and lowercase English letters.

Output Format

Print the length of the longest contiguous \(k\)-alternating substring of \(s\). Print 0 if none exists.

Scoring

The four samples are judged but worth zero points. There are exactly \(20\) scored groups worth \(5\) points each:

• Groups \(1\)–\(4\) (\(20\) points): \(|s|\le 20\) and \(k=1\).
• Groups \(5\)–\(10\) (\(30\) points): \(|s|\le 100\) and \(k\le 2\).
• Groups \(11\)–\(20\) (\(50\) points): no additional constraints.

Sample Input 1

1
aBBdaaa

Sample Output 1

2

Sample Input 2

3
DDaasAAbbCC

Sample Output 2

3

Sample Explanation 2

A valid answer may contain just one uppercase or lowercase block of length \(k\); a case change is not required.

Sample Input 3

2
aafAXbbCDCCC

Sample Output 3

8

Sample Input 4

3
DDaaAAbbCC

Sample Output 4

0

Source

APCS October 2017, implementation problem 2; statement and original image adapted from ZeroJudge c462, “Alternating Strings”.