文字列操作（区間分割・連長圧縮）

問題

文字列 $ S $ が与えられます。

これは、１つ以上の 単語 を連結したものとなっています。

各単語は２文字以上であり、最初の文字と最後の文字が大文字で、残りの文字は小文字となっています。

これらの単語を辞書順に並べて（大文字小文字の違いは無視）、その順に連結して出力して下さい。

解法・ソースコード

この問題は 連長圧縮 と同じ方法で解くことができます。

添え字 $ i $ を先頭から順に動かしながら、下記のように処理していきます。

🔹 大文字 $ s[i] $ に対して、その次の大文字がどこにあるのか探す。
　 その大文字を $ s[j] $ とする。
🔹 $ s[i] $ から $ s[j] $ までの部分文字列を１つの単語として切り出す。
🔹 $ i = j + 1 $ と更新する。
　 $ j $ は単語の終わりを表す添え字なので、その次の $ j + 1 $ に $ i $ を移動する。

上記の処理で取り出した単語のリストをソートして、連結して出力します。　

大文字小文字を無視した状態での辞書順比較は sorted(words, key=str.lower) として行うことができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#--------- 入力例 ----------
s = "FisHDoGCaTAAAaAAbCAC"
#---------------------------
words = []      # 単語のリスト

# 文字列 s を単語ごとに分解する
i = 0
while i < len(s):
    j = i + 1   # s[j] が大文字になる j を見つける
    while j < len(s) and s[j].islower():
        j += 1
    # 単語を切り出してリストに追加
    words.append(s[i:j + 1])

    i = j + 1       # i を j + 1 に移動

# 単語を大文字小文字を無視した状態でソート
words = sorted(words, key=str.lower)

print('解：', ''.join(words))

[実行結果]

解： AAAaAAbCACCaTDoGFisH

問題文で指示された通りの文字列を出力することができました。