# APCS實作題2017年10月第2題：交錯字串 (Alternating Strings)

> 第1版：2023年2月23日
> 第2版：2023年6月11日，加上 C++ 程式碼
> 作者：王一哲
> 題目來源：[106年10月28日實作題第2題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1061028APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c462)

<br />

## 題目

### 問題描述

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

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

### 輸入格式

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

### 輸出格式

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

### 範例一：輸入

1
aBBdaaa

### 範例一：正確輸出

2

<br />

### 範例二：輸入

3
DDaasAAbbCC

### 範例二：正確輸出

3

<br />

### 範例三：輸入

2
aafAXbbCDCCC

### 範例三：正確輸出

8

<br />

### 範例四：輸入

3
DDaaAAbbCC

### 範例四：正確輸出

0

<br />

### 評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依正確通過測資筆數給分。其中：
- 第 1 子題組 20 分，字串長度不超過 20 且 $k = 1$。
- 第 2 子題組 30 分，字串長度不超過 100 且 $k \leq 2$。
- 第 3 子題組 50 分，字串長度不超過 100,000 且無其他限制。

<br />

### 提示

根據定義，要找的答案是大寫片段與小寫片段交錯串接而成。本題有多種解法的思考方式，其中一種是從左往右掃描輸入字串，我們需要紀錄的狀態包含：目前是在小寫子字串中還是大寫子字串中，以及在目前大(小)寫子字串的第幾個位置。根據下一個字母的大小寫，我們需要更新狀態並且記錄以此位置為結尾的最長交替字串長度。

另外一種思考是先掃描一遍字串，找出每一個連續大(小)寫片段的長度並將其記錄在一個陣列，然後針對這個陣列來找出答案。

## Python 程式碼

### 方法1：依序讀取字串的每個字母，記錄字母的大、小寫狀態同時計算最長的交錯字串長度

# 讀取題目要求的交錯字串長度 k 以及字串 data
k = int(input())
data = input()

# 若 k 等於1，則目前的字串長度 length、最長的字串長度 longest 皆設定為1，反之設定為0
if k == 1:
    length, longest = 1, 1
else:
    length, longest = 0, 0

# 讀取開頭的字母
if data[0].isupper():
    uppers, lowers, capital = 1, 0, True
else:
    uppers, lowers, capital = 0, 1, False

# 讀取索引值為1到最後一個字母，有4種狀況
for i in range(1, len(data)):
    if data[i].isupper() and capital: # 這個字母是大寫、前一個字母也是大寫
        uppers += 1
        lowers = 0
        if uppers == k:
            length += k
            longest = max(longest, length)
        if uppers > k:
            length = k
    elif data[i].islower() and capital: # 這個字母是小寫、前一個字母是大寫
        if uppers < k:
            length = 0
        uppers = 0
        lowers = 1
        capital = False
        if k == 1:
            length += 1
            longest = max(longest, length)
    elif data[i].isupper() and not capital: # 這個字母是大寫、前一個字母是小寫
        if lowers < k:
            length = 0
        uppers = 1
        lowers = 0
        capital = True
        if k == 1:
            length += 1
            longest = max(longest, length)
    elif data[i].islower() and not capital: # 這個字母是小寫、前一個字母也是小寫
        uppers = 0
        lowers += 1
        if lowers == k:
            length += k
            longest = max(longest, length)
        if lowers > k:
            length = k
            
print(longest) # 印出最長的交錯字串長度

<br />

依照提示，依序讀取字串的每個字母，記錄字母的大、小寫狀態同時計算最長的交錯字串長度。程式碼的第18 ~ 52行共有4種狀況：

1. 第19 ~ 26行：這個字母是大寫、前一個字母也是大寫，先將連續大寫字母數量 uppers 加 1，連續小寫字母數量 lowers 歸零。接下來又分為兩種狀況：
1. uppers 等於 k，將目前的交錯字串長度 length 加 k，再用 max 更新最長的交錯字串長度 longest。
2. uppers 大於 k，代表這組連續大寫字母可能是下一組交錯字串的開頭，將 length 設定為 k。
2. 第27 ~ 35行：這個字母是小寫、前一個字母是大寫，主要分為3個步驟
1. 如果在這個字母之前的連續大寫字母數量 uppers 小於 k，代表這個字母可能是新的交錯字串開頭，先將 length 歸零。
2. 將 uppers 設定為 0、lowers 設定為 1、字母大寫狀態 capital 設定為 False。
3. 如果 k 等於 1，將 length 加 1，再用 max 更新最長的交錯字串長度 longest。
3. 第36 ~ 44行：這個字母是大寫、前一個字母是小寫，主要分為3個步驟
1. 如果在這個字母之前的連續小寫字母數量 lowers 小於 k，代表這個字母可能是新的交錯字串開頭，先將 length 歸零。
2. 將 uppers 設定為 1、lowers 設定為 0、字母大寫狀態 capital 設定為 True。
3. 如果 k 等於 1，將 length 加 1，再用 max 更新最長的交錯字串長度 longest。
4. 第45 ~ 52行：這個字母是小寫、前一個字母也是小寫，先將連續小寫字母數量 lowers 加 1，連續大寫字母數量 uppers 歸零。接下來又分為兩種狀況：
1. lowers 等於 k，將目前的交錯字串長度 length 加 k，再用 max 更新最長的交錯字串長度 longest。
2. lowers 大於 k，代表這組連續小寫字母可能是下一組交錯字串的開頭，將 length 設定為 k。

ZeroJudge 測試結果，花費時間為 45 ms，使用記憶體 3.4 MB，通過測試。

<br /><br />

### 方法2：先找出連續大寫或小寫的字母數量

# 讀取題目要求的交錯字串長度 k 以及字串 data
k = int(input())
data = input()

# 將連續的大寫或小寫字母數量儲存到串列 data2
data2 = []

# 讀取開頭的字母
if data[0].isupper():
    uppers, lowers, capital = 1, 0, True
else:
    uppers, lowers, capital = 0, 1, False

# 讀取索引值為1到最後一個字母，有4種狀況
for i in range(1, len(data)):
    if data[i].isupper() and capital: # 這個字母是大寫、前一個字母也是大寫
        uppers += 1
        lowers = 0
    elif data[i].islower() and capital: # 這個字母是小寫、前一個字母是大寫
        data2.append(uppers)
        uppers = 0
        lowers = 1
        capital = False
    elif data[i].isupper() and not capital: # 這個字母是大寫、前一個字母是小寫
        data2.append(lowers)
        uppers = 1
        lowers = 0
        capital = True
    elif data[i].islower() and not capital: # 這個字母是小寫、前一個字母也是小寫
        uppers = 0
        lowers += 1

# 加上最後一組連續大寫或小寫字母的長度
if data[-1].isupper(): data2.append(uppers)
else: data2.append(lowers)

# 讀取 data2 索引值為 0 的元素，若大於等於 k，
# 則目前的交錯字串長度 length、最長的字串長度 longest 皆設定為k，反之設定為0
if data2[0] >= k: length = longest = k
else: length = longest = 0

# 讀取 data2 索引值為 1 到最後一個元素，有5種狀況
for i in range(1, len(data2)):
    if data2[i-1] == k and data2[i] == k: # 前一組與這一組字串長度皆等於k
        length += k
        longest = max(longest, length)
    elif data2[i-1] > k and data2[i] == k: # 前一組字串長度大於k，這一組字串長度等於k
        length = 2*k
        longest = max(length, longest)
    elif data2[i-1] < k and data2[i] == k: # 前一組字串長度小於k，這一組字串長度等於k
        length = k
        longest = max(length, longest)
    elif data2[i-1] == k and data2[i] > k: # 前一組字串長度等於k，這一組字串長度大於k
        length += k
        longest = max(length, longest)
        length = 0
    else: # 其它狀況，字串長度 length 歸零
        length = 0

print(longest) # 印出最長的交錯字串長度

<br />

依照提示，先找出連續大寫或小寫的字母數量，記錄在串列 data2 之中，對應到程式碼的第6 ~ 35行，這部分的程式碼運作原則與方法1相同。接下來在第43 ~ 58行，計算交錯字串長度，有5種狀況：

1. 第44 ~ 46行：前一組與這一組字串長度皆等於 k，代表交錯字串長度還有可能會更長，先將 length 加 k，再用 max 更新最長的交錯字串長度 longest。
2. 第47 ~ 49行：前一組字串長度大於 k，這一組字串長度等於 k，代表前一組字串為交錯字串的開頭，先將 length 設定為 2\*k，再用 max 更新最長的交錯字串長度 longest。
3. 第50 ~ 52行：前一組字串長度小於 k，這一組字串長度等於 k，代表這一組字串為交錯字串的開頭，先將 length 設定為 k，再用 max 更新最長的交錯字串長度 longest。
4. 第53 ~ 56行：前一組字串長度等於 k，這一組字串長度大於 k，代表這一組字串為交錯字串的結尾，先將 length 加 k，再用 max 更新最長的交錯字串長度 longest，最後將 length 歸零。
5. 第57、58行：其它狀況，將 length 歸零。

由於這個方法比方法1多執行一個 for 迴圈，理論上執行時間較長。於 ZeroJudge 測試，花費時間為 57 ms，使用記憶體 3.5 MB，通過測試。

<br /><br />

## C++ 程式碼

### 方法1：依序讀取字串的每個字母，記錄字母的大、小寫狀態同時計算最長的交錯字串長度

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[]) {
    // 由標準輸入讀取題目要求的交錯字串長度 k 以及字串 data
    int k;
    cin >> k;
    string data;
    cin >> data;
    
    // 若 k 等於1，則目前的字串長度 length、最長的字串長度 longest 皆設定為1，反之設定為0
    int length, longest;
    if (k == 1) {
        length = 1; longest = 1;
    } else {
        length = 0, longest = 0;
    }
    
    // 讀取開頭的字母
    int uppers, lowers, capital;
    if (isupper(data[0])) {
        uppers = 1; lowers = 0; capital = 1;
    } else {
        uppers = 0; lowers = 1; capital = 0;
    }
    
    // 讀取索引值為1到最後一個字母，有4種狀況
    for(int i=1; i<data.length(); i++) {
        if (isupper(data[i]) && capital == 1) {  // 這個字母是大寫、前一個字母也是大寫
            uppers++; lowers = 0;
            if (uppers == k) {
                length += k;
                longest = max(longest, length);
            }
            if (uppers > k) length = k;
        } else if (islower(data[i]) && capital == 1) {  // 這個字母是小寫、前一個字母是大寫
            if (uppers < k) length = 0;
            uppers = 0; lowers = 1; capital = 0;
            if (k == 1) {
                length++;
                longest = max(longest, length);
            }
        } else if (isupper(data[i]) && capital == 0) {  // 這個字母是大寫、前一個字母是小寫
            if (lowers < k) length = 0;
            uppers = 1; lowers = 0; capital = 1;
            if (k == 1) {
                length++;
                longest = max(longest, length);
            }
        } else if (islower(data[i]) && capital == 0) {  // 這個字母是小寫、前一個字母也是小寫
            uppers = 0; lowers++;
            if (lowers == k) {
                length += k;
                longest = max(longest, length);
            }
            if (lowers > k) length = k;
        }
    }
    cout << longest << endl;
    return 0;
}

<br />

依照提示，依序讀取字串的每個字母，記錄字母的大、小寫狀態同時計算最長的交錯字串長度。程式碼的第29 ~ 59行共有4種狀況：

1. 第30 ~ 36行：這個字母是大寫、前一個字母也是大寫，先將連續大寫字母數量 uppers 加 1，連續小寫字母數量 lowers 歸零。接下來又分為兩種狀況：
1. uppers 等於 k，將目前的交錯字串長度 length 加 k，再用 max 更新最長的交錯字串長度 longest。
2. uppers 大於 k，代表這組連續大寫字母可能是下一組交錯字串的開頭，將 length 設定為 k。
2. 第37 ~ 43行：這個字母是小寫、前一個字母是大寫，主要分為3個步驟
1. 如果在這個字母之前的連續大寫字母數量 uppers 小於 k，代表這個字母可能是新的交錯字串開頭，先將 length 歸零。
2. 將 uppers 設定為 0、lowers 設定為 1、字母大寫狀態 capital 設定為 0。
3. 如果 k 等於 1，將 length 加 1，再用 max 更新最長的交錯字串長度 longest。
3. 第44 ~ 50行：這個字母是大寫、前一個字母是小寫，主要分為3個步驟
1. 如果在這個字母之前的連續小寫字母數量 lowers 小於 k，代表這個字母可能是新的交錯字串開頭，先將 length 歸零。
2. 將 uppers 設定為 1、lowers 設定為 0、字母大寫狀態 capital 設定為 1。
3. 如果 k 等於 1，將 length 加 1，再用 max 更新最長的交錯字串長度 longest。
4. 第51 ~ 58行：這個字母是小寫、前一個字母也是小寫，先將連續小寫字母數量 lowers 加 1，連續大寫字母數量 uppers 歸零。接下來又分為兩種狀況：
1. lowers 等於 k，將目前的交錯字串長度 length 加 k，再用 max 更新最長的交錯字串長度 longest。
2. lowers 大於 k，代表這組連續小寫字母可能是下一組交錯字串的開頭，將 length 設定為 k。

ZeroJudge 測試結果，花費時間為 4 ms，使用記憶體 388 kB，通過測試。

<br /><br />

### 方法2：先找出連續大寫或小寫的字母數量

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int main(int argc, char* argv[]) {
    // 由標準輸入讀取題目要求的交錯字串長度 k 以及字串 data
    int k;
    cin >> k;
    string data;
    cin >> data;
    
    // 將連續的大寫或小寫字母數量儲存到串列 data2
    deque<int> data2;
    
    // 讀取開頭的字母
    int uppers, lowers, capital;
    if (isupper(data[0])) {
        uppers = 1; lowers = 0; capital = 1;
    } else {
        uppers = 0; lowers = 1; capital = 0;
    }
    
    // 讀取索引值為1到最後一個字母，有4種狀況
    for(int i=1; i<data.length(); i++) {
        if (isupper(data[i]) && capital == 1) {  // 這個字母是大寫、前一個字母也是大寫
            uppers++; lowers = 0;
        } else if (islower(data[i]) && capital == 1) {  // 這個字母是小寫、前一個字母是大寫
            data2.push_back(uppers);
            uppers = 0; lowers = 1; capital = 0;
        } else if (isupper(data[i]) && capital == 0) {  // 這個字母是大寫、前一個字母是小寫
            data2.push_back(lowers);
            uppers = 1; lowers = 0; capital = 1;
        } else if (islower(data[i]) && capital == 0) {  // 這個字母是小寫、前一個字母也是小寫
            uppers = 0; lowers++;
        }
    }
    
    // 加上最後一組連續大寫或小寫字母的長度
    if (isupper(data[data.length()-1])) data2.push_back(uppers);
    else data2.push_back(lowers);
    
    // 讀取 data2 索引值為 0 的元素，若大於等於 k，
    // 則目前的交錯字串長度 length、最長的字串長度 longest 皆設定為k，反之設定為0
    int length, longest;
    if (data2[0] >= k) {
        length = k; longest = k;
    } else {
        length = 0; longest = 0;
    }
    
    // 讀取 data2 索引值為 1 到最後一個元素，有5種狀況
    for(int i=1; i<data2.size(); i++) {
        if (data2[i-1] == k && data2[i] == k) {  // 前一組與這一組字串長度皆等於k
            length += k;
            longest = max(length, longest);
        } else if (data2[i-1] > k && data2[i] == k) {  // 前一組字串長度大於k，這一組字串長度等於k
            length = 2*k;
            longest = max(length, longest);
        } else if (data2[i-1] < k && data2[i] == k) {  // 前一組字串長度小於k，這一組字串長度等於k
            length = k;
            longest = max(length, longest);
        } else if (data2[i-1] == k && data2[i] > k) {  // 前一組字串長度等於k，這一組字串長度大於k
            length += k;
            longest = max(length, longest);
            length = 0;
        } else {  // 其它狀況，字串長度 length 歸零
            length = 0;
        }
    }
    cout << longest << endl;
    return 0;
}

<br />

依照提示，先找出連續大寫或小寫的字母數量，記錄在 data2 之中，對應到程式碼的第14 ~ 41行，這部分的程式碼運作原則與方法1相同。接下來在第53 ~ 70行，計算交錯字串長度，有5種狀況：

1. 第54 ~ 56行：前一組與這一組字串長度皆等於 k，代表交錯字串長度還有可能會更長，先將 length 加 k，再用 max 更新最長的交錯字串長度 longest。
2. 第57 ~ 59行：前一組字串長度大於 k，這一組字串長度等於 k，代表前一組字串為交錯字串的開頭，先將 length 設定為 2\*k，再用 max 更新最長的交錯字串長度 longest。
3. 第60 ~ 62行：前一組字串長度小於 k，這一組字串長度等於 k，代表這一組字串為交錯字串的開頭，先將 length 設定為 k，再用 max 更新最長的交錯字串長度 longest。
4. 第63 ~ 66行：前一組字串長度等於 k，這一組字串長度大於 k，代表這一組字串為交錯字串的結尾，先將 length 加 k，再用 max 更新最長的交錯字串長度 longest，最後將 length 歸零。
5. 第67、68行：其它狀況，將 length 歸零。

由於這個方法比方法1多執行一個 for 迴圈，理論上執行時間較長。於 ZeroJudge 測試，花費時間為 4 ms，使用記憶體 384 kB，通過測試。

<br /><br />

## 參考資料

參考資料：吳燦銘（2020）。**APCS大學程式設計先修檢測：C++超效解題致勝祕笈**。新北市：博碩文化。 8-7

<br />

---

###### tags:`APCS`、`Python`