TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

50.0% (2/4)

Tags

Description

一個字串如果全由大寫英文字母組成,我們稱為大寫字串;如果全由小寫字母組成則稱為小寫字串。字串的長度是他所包含字母的個數,在本題中,字串均由大小寫英文字母組成。假設 $k$ 是一個自然數,一個字串被稱為「$k$-交錯字串」,如果它是由長度為 $k$ 的大寫字串與長度為 $k$ 的小寫字串交錯串接組成。

舉例來說,StRiNg 是一個 $1$-交錯字串,因為它是一個大寫一個小寫交替出現;而 heLLow 是一個 $2$-交錯字串,因為它是兩個小寫接兩個大寫再接兩個小寫。但不管 $k$ 是多少,aBBaaaBaBaBBaaaAAbbCCCC 都不是 $k$-交錯字串。

本題的目標是對於給定 $k$ 值,在一個輸入字串找出最長一段連續子字串滿足 $k$-交錯字串的要求。例如 $k=2$ 且輸入 aBBaaa,最長的 $k$-交錯字串是 BBaa,長度為 $4$。又如 $k=1$ 且輸入 BaBaBB,最長的 $k$-交錯字串是 BaBaB,長度為 $5$。

請注意,滿足條件的子字串可能只包含一段小寫或大寫字母而無交替,如範例二。此外,也可能不存在滿足條件的子字串,如範例四。

Input Format

輸入的第一行是 $k$,第二行是輸入字串,字串長度至少為 $1$,只由大小寫英文字母組成(也就是 AZaz)並且沒有空白。

  • 字串長度不超過 $100000$

Output Format

輸出輸入字串中滿足 $k$-交錯字串的要求的最長一段連續子字串的長度,以換行結尾。

Sample Input 1

1
aBBdaaa

Sample Output 1

2

Sample Input 2

3
DDaasAAbbCC

Sample Output 2

3

Sample Input 3

2
aafAXbbCDCCC

Sample Output 3

8

Sample Input 4

3
DDaaAAbbCC

Sample Output 4

0

Hints

Problem Source

APCS 考古

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 4~9 字串長度不超過 $20$ 且 $k=1$ 20
3 10~17 字串長度不超過 $100$ 且 $k\le 2$ 30
4 0~27 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 1 4
3 1000 524288 65536 1 4
4 1000 524288 65536 2 4
5 1000 524288 65536 2 4
6 1000 524288 65536 2 4
7 1000 524288 65536 2 4
8 1000 524288 65536 2 4
9 1000 524288 65536 2 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 3 4
16 1000 524288 65536 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 4
19 1000 524288 65536 4
20 1000 524288 65536 4
21 1000 524288 65536 4
22 1000 524288 65536 4
23 1000 524288 65536 4
24 1000 524288 65536 4
25 1000 524288 65536 4
26 1000 524288 65536 4
27 1000 524288 65536 4