交錯字串 (APCS 2017-10 中級)

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

舉例來說，「StRiNg」是一個 1-交錯字串，因為它是一個大寫一個小寫交替出現；而「heLLow」是一個 2-交錯字串，因為它是兩個小寫接兩個大寫再接兩個小寫。但不管 k 是多少，「aBBaaa」、「BaBaBB」、「aaaAAbbCCCC」都不是 k-交錯字串。

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

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

輸入格式

輸入的第一行是 k，第二行是輸入字串，字串長度至少為 1，只由大小寫英文字母組成 (A~Z, a~z) 並且沒有空白。

輸出格式

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

範例輸入 1

1
aBBdaaa

範例輸出 1

2

範例輸入 2

3
DDaasAAbbCC

範例輸出 2

3

範例輸入 3

2
aafAXbbCDCCC

範例輸出 3

8

範例輸入 4

3
DDaaAAbbCC

範例輸出 4

0

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制 (time limit) 均為 1 秒，依正確通過測資筆數給分。 其中：

第 1 子題組 20 分，字串長度不超過 20 且 k=1。

第 2 子題組 30 分，字串長度不超過 100 且 k ≤ 2。

第 3 子題組 50 分，字串長度不超過 100,000 且無其他限制。

題目來源

APCS 2017 年 10 月實作題第 2 題；題目與原始圖片參考 ZeroJudge c462「交錯字串」。

• APCS 官方歷屆試題（2017/10/28 實作題 PDF）