ここからこの質問を受け取りました。しかし、私が理解できるアルゴリズムの実行時間は本当に悪かった. 質問は次のとおりです。
s のすべての文字が異なる場合、文字列 s は一意であると呼ばれます。文字列 s2 は、s1 のいくつかの文字を削除して s2 を得ることができれば、文字列 s1 から生成できます。
文字列 s1 が文字列 s2 よりも美しいのは、s1 の長さが s2 の長さより長い場合、またはそれらの長さが等しく、s1 が辞書編集的に s2 よりも大きい場合です。
文字列 s が与えられた場合、s から生成できる最も美しい一意の文字列を見つける必要があります。
入力: 入力の最初の行は、1,000,000(10^6) 文字以下の文字列 s です。s の文字はすべて小文字の英字です。
出力: s から生成できる最も美しい一意の文字列を出力します
サンプル入力: ババブ
サンプル出力: ba
私がしたことはこれです：
- 文字列を取得し、隣接するすべての等しい文字を 1 つだけ削除します。例: 入力: "bbbbbab" 出力: "bab"、これはこのステップの出力です。次のステップへのインプットになります。
- 次に、文字列内の一意の文字ごとに配列を作成します。この配列には、指定された入力配列での出現のインデックスが含まれます。
- 各要素の最初の出現に注意してください。発生の最小値と最大値を見つけます。この反復を使用して、インデックス max で終わる単語で形成できるすべての可能な文字列を反復処理します。辞書編集的に最大のものを取ります。
- 最大を移動して上記を繰り返します。
入力文字列が非常に大きい場合にスケーリングできる、正確で効率的なアルゴリズムが必要です。