Editorial for 交錯字串 (APCS 2017-10 中級)
簡潔題意
給一個正整數 \(k\) 和一個只有大小寫英文字母的字串。把一個字串切成每段長度都是 \(k\) 的小段，每一小段全是大寫或全是小寫，而且相鄰兩段的大小寫相反，這樣的字串叫 \(k\)-交錯字串（只有一小段也算）。求輸入字串裡最長的一段連續子字串是 \(k\)-交錯字串的長度，沒有就輸出 \(0\)（字串長度不超過 \(100000\)）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(20\) 分）：字串長度不超過 \(20\) 且 \(k = 1\)。
- 子題組 2（\(30\) 分）：字串長度不超過 \(100\) 且 \(k \le 2\)。
- 子題組 3（\(50\) 分）：無額外限制。
先拿下子題組 1（20 分）：k = 1 就是「大小寫一直交替」的最長一段
\(k = 1\) 時每一小段就是一個字母，所以 \(1\)-交錯字串只要求相鄰兩個字母的大小寫不一樣。從左往右掃一遍，用 now 記「以目前這個字母結尾、大小寫一直交替的最長長度」：這個字母跟前一個字母大小寫不同，就接著前面繼續長（now++）；相同就斷掉，從這個字母重新算（now = 1）。每走一步拿 now 跟擂台 ans 比（上冊 3.9 的擂台法，這裡用 7.6 的 max 一句寫完）。
判斷大小寫用 8.5 的 islower。不過 8.5 提醒過：islower 回傳的是「非零／零」而不是 true／false，兩個「非零」不保證相等，不要拿兩個 islower 的結果直接互相比較（本站環境剛好會過，但標準沒有保證）——包一層判斷函式（上冊 7.4）先轉成 bool 再比，之後每一份程式都用它。
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
using namespace std;
// c 是小寫字母嗎？islower 回傳的是非零／零，先轉成 bool 才能拿來互相比較
bool my_islower(char c) {
return islower(c) != 0;
}
int main() {
int k;
cin >> k; // 子題組 1 保證 k = 1：讀進來放著就好
string s;
cin >> s;
int n = (int)s.size();
int now = 1, ans = 1; // now＝以目前這個字母結尾、大小寫一直交替的最長長度；第 0 個字母自己算 1
for (int i = 1; i < n; i++) {
if (my_islower(s[i]) == my_islower(s[i - 1])) {
now = 1; // 跟前一個字母同大小寫：交替斷掉，從這個字母重新算
} else {
now++; // 大小寫換了：接著前面繼續長
}
ans = max(ans, now);
}
cout << ans << '\n';
return 0;
}
拿範例 1 對一次：aBBdaaa 的 now 依序是 \(1, 2, 1, 2, 1, 1, 1\)，最大 \(2\)。這份程式交上去，範例 2～4 會 WA——這是正常的，逐筆給分之下子題組 1 的 \(20\) 分穩穩到手。
從 20 分到 100 分：先切成「連續同大小寫」的一段一段，再一段一段接
字串有十萬個字母，把所有子字串列舉出來逐一檢查是 \(10^{10}\) 級的工作量，滿分一定要「掃一遍就出答案」。關鍵觀察：交錯字串的每一小段是恰好 \(k\) 個同大小寫的字母，相鄰兩小段大小寫相反——所以先把整個字串切成一段一段最長的連續同大小寫，每一段只記長度就夠了。範例 3 的 aafAXbbCDCCC（\(k = 2\)）切成 aaf／AX／bb／CDCCC，長度 \(3, 2, 2, 5\)。
接著一段一段看。用 now 記「以這一段結尾、最長的交錯字串長度」，一段的長度 x 只有三種情況：
x == k：這一段剛好是一小段，接在前面那串後面，now += k。x < k：這一段連一小段都湊不成，前面那串到這裡斷掉，now = 0。x > k：這一段的前 \(k\) 個字母可以當前面那串的最後一小段（now += k，但接完就到底了——再往右是同大小寫的字母，先把這個長度記進擂台）；這一段的後 \(k\) 個字母可以當新一串的第一小段，往右繼續接（now = k）；中間的字母沒有人要。
每看完一段都拿 now 跟擂台比。範例 3 的 \(3, 2, 2, 5\)：aaf 只取後兩個 af，now = 2；AX 接上 \(4\)；bb 接上 \(6\)；CDCCC 前兩個 CD 接上變 \(8\)、記下來，再以後兩個 CC 重新開始 now = 2——答案 \(8\)。範例 2 的 DDaasAAbbCC（\(k = 3\)）切成 \(2, 3, 2, 2, 2\)：只有 aas 湊得成一小段，前後都斷掉，答案 \(3\)。
切段的程式：i 指著這一段的開頭，j 從 i + 1 一路往右走到大小寫變了為止，這一段就是 i 到 j - 1，長度 j - i，記進 vector<int> len（10.2 的 push_back），然後 i 直接跳到 j 開始下一段。第二步用 12.4 的 range-based for 把 len 走一遍。
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
// c 是小寫字母嗎？islower 回傳的是非零／零，先轉成 bool 才能拿來互相比較
bool my_islower(char c) {
return islower(c) != 0;
}
void solve() {
int k;
cin >> k;
string s;
cin >> s;
int n = (int)s.size();
// 第一步：切成一段一段「連續同大小寫」，只記每一段的長度
vector<int> len;
int i = 0; // i＝這一段的開頭
while (i < n) {
int j = i + 1; // j 往右走，走到大小寫跟 s[i] 不一樣的第一個位置
while (j < n && my_islower(s[j]) == my_islower(s[i])) {
j++;
}
len.push_back(j - i); // 這一段是 s[i] ~ s[j-1]，長度 j - i
i = j; // 下一段從 j 開始
}
// 第二步：一段一段接。now＝以這一段結尾、最長的交錯字串長度
int now = 0, ans = 0;
for (int x : len) {
if (x == k) {
now += k; // 剛好一小段：接在前面那串後面
} else if (x < k) {
now = 0; // 連一小段都湊不成：前面那串斷掉
} else {
now += k; // 前 k 個字母當前面那串的最後一小段，接完就到底了
ans = max(ans, now); // 先記下來
now = k; // 後 k 個字母當新一串的第一小段，往右繼續接
}
ans = max(ans, now);
}
cout << ans << '\n';
}
int main() {
solve();
}
x > k 那支裡的 ans = max(ans, now); 不能省：接上前 \(k\) 個字母之後的長度只在那一刻存在，下一行 now = k 就把它蓋掉了。兩步各掃一遍字串，十萬個字母也是一眨眼。
更簡潔的寫法：不先切段，一個字母一個字母邊讀邊算
上面先切段再接，要把字串存起來掃兩遍。其實可以一個字母一個字母讀、讀到一個就處理一個——連字串都不用存。訣竅是讓 now 多容忍一點：now 記「以目前這個字母結尾、還有機會湊成交錯字串的最長長度」——前面是一小段一小段湊滿的，最後一小段可以還沒湊滿，now % k 就是最後一小段目前填了幾個字母（\(0\) 代表剛好湊滿）。每讀一個字母，看它跟前一個字母的大小寫同不同、最後一小段滿不滿，一共四種情況：
最後一小段還沒滿（now % k != 0） |
最後一小段剛好滿（now % k == 0） |
|
|---|---|---|
| 跟前一個字母同大小寫 | 再填一個進去：now++ |
同大小寫已經超過 \(k\) 個：只剩「最後 \(k\) 個字母」這一小段能算，now = k |
| 大小寫換了 | 沒滿的那一小段永遠湊不滿了：前面全部作廢，這個字母重新開一小段，now = 1 |
前面的小段都剛好湊滿：這個字母開新的一小段接上去，now++ |
答案只算湊滿的部分：now / k * k 把沒滿的尾巴去掉（整數除法先無條件捨去再乘回來，上冊 2.6），拿去跟擂台比。讀入用 8.4 的 cin >> c（跳過換行、一次一個字母），放進迴圈條件讀到沒有為止——第一個字母沒有「前一個」可比，單獨當一種情況。
#include <iostream>
#include <cctype>
#include <algorithm>
using namespace std;
// c 是小寫字母嗎？islower 回傳的是非零／零，先轉成 bool 才能拿來互相比較
bool my_islower(char c) {
return islower(c) != 0;
}
void solve() {
int k;
cin >> k;
int now = 0, ans = 0; // now＝以目前這個字母結尾、還有機會湊成交錯字串的最長長度（最後一小段可以沒滿）
char c, last_c; // c＝現在這個字母，last_c＝前一個字母
for (int i = 0; cin >> c; i++) { // 一個字母一個字母讀，讀到沒有為止
if (i == 0) {
now = 1; // 第一個字母：自己開一小段
} else if (my_islower(c) == my_islower(last_c)) { // 跟前一個字母同大小寫
if (now % k != 0) {
now++; // 最後一小段還沒滿：再填一個進去
} else {
now = k; // 剛好滿了又來一個同大小寫：只剩最後 k 個字母能算
}
} else { // 大小寫換了
if (now % k != 0) {
now = 1; // 最後一小段沒滿：前面全部作廢，這個字母重新開一小段
} else {
now++; // 前面都剛好湊滿：開新的一小段接上去
}
}
ans = max(ans, now / k * k); // 只有湊滿的小段才算數：去掉沒滿的尾巴
last_c = c;
}
cout << ans << '\n';
}
int main() {
solve();
}
拿範例 2 的 DDaasAAbbCC（\(k = 3\)）走一遍：now 依序是 \(1, 2, 1, 2, 3, 4, 5, 1, 2, 1, 2\)，now / 3 * 3 最大是 \(3\)。\(k = 1\) 時 now % k 永遠是 \(0\)，表格只剩右邊那一欄——同大小寫 now = 1、換了 now++——正是子題組 1 那支程式。
兩種寫法答案完全一樣、都是滿分。切段版每一步都對應到題目的一句話，想清楚就寫得出來；邊讀邊算版程式短、不用存字串，但「now 可以帶著沒滿的尾巴」這個設定要先想通，四種情況少一格就錯。
測過再交：四個範例抓不到「短段沒有斷掉」
四個範例分別蓋到 \(k = 1\)（範例 1）、只有一小段（範例 2）、長段兩頭各取 \(k\) 個（範例 3）、答案 \(0\)（範例 4）。但有一種錯四個範例全放行：長度不到 \(k\) 的段沒有把前面那串斷掉——範例 2 裡 aas 之後全是短段，沒有東西可以被錯接上去；範例 4 連一小段都湊不成。自己補：
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
2 ／ aaBBcDD |
4 |
c 只有一個、湊不成一小段，aaBB 和 DD 不能接在一起。短段沒斷掉的程式印 6 |
2 ／ aaaa |
2 |
同大小寫連續剛好 \(2k\) 個：兩小段大小寫相同不算交錯，只能算一小段。把長段照 \(k\) 切塊的程式印 4 |
4 ／ abcd |
4 |
整個字串剛好是一小段 |
5 ／ abcd |
0 |
\(k\) 比整個字串還長：一小段都湊不成 |
四筆都親眼看過正確，這題就穩了。
常犯錯誤
- 長度不到 \(k\) 的段沒有把
now歸零：四個範例全過，自測表第 1 列印6（該印4）。 - 長度超過 \(k\) 的段整段丟掉（
now = 0，沒留後 \(k\) 個字母當新起點）：範例 3 印4（該印8）。 - 長段接上前面之後忘了先記擂台就
now = k：範例 3 印6。 - 長段照 \(k\) 切塊全部算進去（
now += x / k * k）：範例 1 印7（該印2）——BB、aaa整段被當成好幾小段接上去；自測表第 2 列印4。 - 邊讀邊算版忘了
/ k * k，沒滿的尾巴也算進答案：範例 2 印5（該印3）。 - 比的是「字母一不一樣」而不是「大小寫一不一樣」（
s[i] == s[i - 1]）：範例 1 印3——Bda被當成交替。 - 以為至少要兩小段才算：範例 2 印
0。