問題描述
一個字串如果全由大寫英文字母組成，我們稱為大寫字串；如果全由小寫字母組成則稱為小寫字串。字串的長度是它所包含字母的個數，在本題中，字串均由大小寫英文字母組成。假設 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。
請注意，滿足條件的子字串可能只包含一段小寫或大寫字母而無交替，如範例二。此外，也可能不存在滿足條件的子字串，如範例四。
評分說明：
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依正確通過測資筆數給分。其中：
第 1 子題組 20 分，字串長度不超過 20 且 k=1。
第 2 子題組 30 分，字串長度不超過 100 且 k ≤ 2。
第 3 子題組 50 分，字串長度不超過 100,000 且無其他限制。
輸入的第一行是 k，第二行是輸入字串，字串長度至少為 1，只由大小寫英文字母組成(A~Z, a~z)並且沒有空白。
輸出輸入字串中滿足 k-交錯字串的要求的最長一段連續子字串的長度，以換行結尾。
範例一：輸入 1 aBBdaaa 範例二：輸入 3 DDaasAAbbCC 範例三：輸入 2 aafAXbbCDCCC 範例四：輸入 3 DDaaAAbbCC
範例一：正確輸出 2 範例二：正確輸出 3 範例三：正確輸出 8 範例四：正確輸出 0
提示：根據定義，要找的答案是大寫片段與小寫片段交錯串接而成。本題有多種解法的思考方式，其中一種是從左往右掃描輸入字串，我們需要紀錄的狀態包含：目前是在小寫子字串中還是大寫子字串中，以及在目前大(小)寫子字串的第幾個位置。根據下一個字母的大小寫，我們需要更新狀態並且記錄以此位置為結尾的最長交替字串長度。
另外一種思考是先掃描一遍字串，找出每一個連續大(小)寫片段的長度並將其記錄在一個陣列，然後針對這個陣列來找出答案。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||