# APCS實作題2018年：最少相異字母

> 日期：2023年9月9日
> 作者：王一哲
> 題目來源：107年10月實作題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=e313)

<br />

## 題目

### 問題描述

「字串裡面有太多不同的字是不和諧的」，喵喵妮維森這麼說著。因此她想要在 N 個字串中，找出含有最少相異字母的字串，當有多個都是最少相異字母時，則選出字典排序最小者。

舉例來說，對於三個字串 "ABBCAAB"、"AABBACC"、"AAPPCCSS"，可以看出各個字串所含有的相異字母數量分別是3、3、4。其中按照字典間互相比較可以得到"ABBCAAB" > "AABBACC"，所以最後會得到字串"AABBACC"。

請幫助喵喵維森找出最和諧的字串。
<br />

### 輸入格式

第一行有一個正整數 N (N ≤ 1000)，代表接下來有 N 個字串。
接下來有 N 行，每一行有一個字串，字串內只會含有大寫字母A ~ Z。
<br />

### 輸出格式

找出 N 個字串內最少相異字母的字串，當有多個字串相異字母都是最少時，則選出字典排序最小者。
<br />

### 範例：輸入

3
ABBCAAB
AABBACC
AAPPCCSS

### 範例：正確輸出

AABBACC

<br />

## Python 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 35 ms，使用記憶體最多約為 5.9 MB，通過測試。

N = int(input())  # 讀取資料行數
data = []         # 字串資料
chars = []        # 每個字串的字母數量
idx = [-1]        # 字母數量最少的字串索引值，先存入 -1
minL = 27         # 最少的字母數量，先存入 27

# 讀取 N 行資料
for i in range(N):
    data.append(input())        # 存入字串
    chars.append(set(data[i]))  # 用 set 格式存入 data[i] 的字母
    if len(chars[i]) < minL:    # 如果 chars[i] 的長度小於 minL
        idx = [i]               # 將 idx 內容重設為 [i]
        minL = len(chars[i])    # minL 重設為 len(chars[i])
    elif len(chars[i]) == minL: # 如果 chars[i] 的長度等於 minL
        idx.append(i)           # 將 idx 內容加入 i

# 比較字母數量相同的字串，依照字母順序找出字母排序較小者
ans = idx[0]   # ans 預設為 idx[0]
for i in range(1, len(idx)):    # 依序取出 idx[1] ~ idx[-1]
    for c1, c2 in zip(data[ans], data[idx[i]]):  # 取出字母
        if c1 < c2:       # 如果 c1 < c2，ans 不變，中斷迴圈
            break
        elif c1 > c2:     # 如果 c1 > c2，ans 重設為 idx[i]，中斷迴圈
            ans = idx[i]
            break

print(data[ans])   # 印出答案

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 60 ms，使用記憶體最多約為 836 kB，通過測試。

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

int main() {
    int N; cin >> N;          // 讀取資料行數
    vector<string> data;      // 字串資料
    vector<size_t> idx;       // 字母數量最少的字串索引值
    size_t minL = 27;         // 最少的字母數量，先存入 27

    /* 讀取 N 行資料 */
    for (int i=0; i<N; i++) {
        string s; cin >> s;   // 讀取字串
        data.push_back(s);    // 存入字串
        set<char> cs (s.begin(), s.end());  // 用 set 格式計算 s 的字母數量
        if (cs.size() < minL) {  // 如果 cs 的長度小於 minL
            idx.clear();         // 將 idx 內容重設為 {i}
            idx.push_back(i);
            minL = cs.size();    // minL 重設為 cs.size()
        } else if (cs.size() == minL) {  // 如果 cs 的長度等於 minL
            idx.push_back(i);    // 將 idx 內容加入 i
        }
    }

    /* 比較字母數量相同的字串，依照字母順序找出字母排序較小者 */
    size_t ans = idx[0];  // ans 預設為 idx[0]
    for(size_t i=1; i<idx.size(); i++) {  // // 依序取出 idx[1] ~ idx[-1]
        char c1, c2;
        for(size_t j = 0; j < min(data[ans].size(), data[idx[i]].size()); j++) {
            c1 = data[ans][j];
            c2 = data[idx[i]][j];
            if (c1 < c2) {  // 如果 c1 < c2，ans 不變，中斷迴圈
                break;
            } else if (c1 > c2) {  // 如果 c1 > c2，ans 重設為 idx[i]，中斷迴圈
                ans = idx[i];
                break;
            }
        }
    }
    cout << data[ans] << endl;  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`