一個字串如果全由大寫英文字母組成,我們稱為大寫字串;如果全由小寫字母組成則稱為小寫字串。字串的長度是他所包含字母的個數,在本題中,字串均由大小寫英文字母組成。假設 $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$-交錯字串的要求的最長一段連續子字串的長度,以換行結尾。
APCS 考古
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 |