565 . 交錯字串

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Kevin Yu

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

30.0% (3/10)

Tags

apcsc apcsc-string

Description

一個字串如果全由大寫英文字母組成，我們稱為大寫字串；如果全由小寫字母組成則稱為小寫字串。字串的長度是他所包含字母的個數，在本題中，字串均由大小寫英文字母組成。假設 $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$。

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

Input Format

輸入的第一行是 $k$，第二行是輸入字串，字串長度至少為 $1$，只由大小寫英文字母組成（也就是 A 到 Z 與 a 到 z）並且沒有空白。

  • 字串長度不超過 $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
Submit
Back to Top