問題定義

与えられた文字列 s から、重複する文字をすべて除去します。ただし、結果の文字列には特定の条件下で複数の要素が存在せず、残るべき一文字のみを残す必要があります。この際、以下の制約を満たさなければなりません。

• 最終的な文字列は、元の文字列に含まれる文字の中で最も小さい辞書順であること。
• 文字列内での各文字の相対的な順序は保たれること。

入力例と期待される出力は以下の通りです。

入力："bcabc"
出力："abc"

入力："cbacdcbc"
出力："acdb"

アルゴリズムの設計思想

この問題は、部分集合の中で最も小さな順序を保つための組み合わせ最適化であり、貪欲戦略（Greedy Strategy）とデータ構造「単調スタック」を組み合わせることで効率的に解決できます。主な目標は、現在の結果に対してより小さな文字が後方に存在する場合、その小さな文字のために今の大きい文字を削除できるかどうかを判断することです。

具体的なプロセスは以下の論理フローに従います。

1. 頻度の管理： 各文字列内の各文字の総出現回数を事前にカウントします。
2. スタックの運用： 結果となる文字列を構成するためにスタックを使用します。スタックの中身は常に辞書順の昇順（単調性）を維持するように調整を行います。
3. 判定ロジック： 新しい文字を処理する際、すでに結果に含まれている場合はスキップします。含まれていない場合、以下の条件を確認してスタックトップと比較します。
4. 現在の文字がスタックトップより小さい場合、かつスタックトップの文字がまだ後に登場する回数がある場合は、その大きな文字をポップ（取り出し）して、より小さい文字が先に配置できるように変更します。
5. 最終的にすべての文字を走査した後、スタックの中身を結合することで、条件を満たす最小の文字列が得られます。

実装の詳細

コードでは、整数配列を使用して各アルファベットの残り出現回数和、スタックに含まれているか否かのフラグを管理しています。これにより、O(N) の時間計算量で処理が可能です。

public String getSmallestUniqueSequence(String input) {
    // 各文字の出現頻度を記録するための配列（小文字アルファベット限定）
    int[] remainingCounts = new int[26];
    
    // 結果文字列に含まれているかを追跡する配列
    boolean[] inResult = new boolean[26];
    
    // 入力文字列全体の出現回数をカウント
    for (int i = 0; i < input.length(); i++) {
        remainingCounts[input.charAt(i) - 'a']++;
    }
    
    // データ構造として双端キュー（Deque）をスタックとして利用
    java.util.Deque<Character> stack = new java.util.ArrayDeque<>();
    
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        
        // もし既に処理済み（スタック内）であれば、出現回数のみを減らして次へ
        if (inResult[c - 'a']) {
            remainingCounts[c - 'a']--;
            continue;
        }
        
        // ストックが空でないかつ、頂点が現在の文字より大きく、かつ頂点文字がまだ後で使われる場合
        while (!stack.isEmpty() && stack.peekLast() > c && remainingCounts[stack.peekLast() - 'a'] > 0) {
            char popped = stack.pollLast();
            inResult[popped - 'a'] = false;
        }
        
        // 現在の文字をスタックに追加し、包含状態をフラグを立てる
        stack.offerLast(c);
        inResult[c - 'a'] = true;
        
        // 使用した分、残り回数を減算
        remainingCounts[c - 'a']--;
    }
    
    // ストックの内容を連結して戻り値とする
    StringBuilder sb = new StringBuilder();
    for (char ch : stack) {
        sb.append(ch);
    }
    
    return sb.toString();
}