ZeroJudge 解題筆記：e837. P4. 字母排列 (Letters)

作者：王一哲
日期：2025年2月10日



ZeroJudge 題目連結：e837. P4. 字母排列 (Letters)

解題想法

這題的說明不精準，題目中說要找按照順序排列的最長字串，實際上是要找按照順序且相鄰字母的最長字串。

Python 程式碼

使用時間約為 26 ms，記憶體約為 3.3 MB，通過測試。

import sys

for s in sys.stdin:
    s = s.strip()  # 去掉最後面的 \0
    now = s[0]  # 目前符合要求的最長字串，先放入 s[0]
    ans = ""  # 答案
    for c in s[1:]:  # 依序讀取 s[1] ~ s[-1]
        if ord(c) == ord(now[-1])+1: now += c # 如果 c 是 now[-1] 的下一個字母，將 c 接到 now 之後
        else:  # 如果 c 不是 now[-1] 的下一個字母
            if len(now) >= len(ans): ans = now  # 如果 now 的長度大於等於 ans 的長度，更新 ans
            now = c  # 更新 now
    if len(now) >= len(ans): ans = now  # 最後要再檢查一次 now 是否比 ans 長
    print(f"{len(ans):d} {ans:s}")  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 384 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;  // 輸入的字串
    while(cin >> s) {
        string now = "", ans = "";  // 目前符合要求的最長字串；答案
        now += s[0];  // 先放入 s[0]
        for(char c : s.substr(1)) {  // 依序讀取 s[1] ~ s[-1]
            if (c == now.back()+1) {  // 如果 c 是 now.back() 的下一個字母
                now += c;  // 將 c 接到 now 之後
            } else {  // 如果 c 不是 now.back() 的下一個字母
                if (now.size() >= ans.size()) ans = now;  // 如果 now 的長度大於等於 ans 的長度，更新 ans
                now = c;  // 更新 now
            }
        }
        if (now.size() >= ans.size()) ans = now;  // 最後要再檢查一次 now 是否比 ans 長
        cout << ans.size() << " " << ans << "\n";  // 印出答案
    }
    return 0;
}