C++で文字列から重複する文字を削除し、辞書順最小の結果を得る方法

問題概要

小文字の英字のみで構成された文字列 s が与えられます。この文字列から重複する文字をすべて取り除き、各文字がちょうど1回だけ出現するようにします。そのうえで、結果の文字列が辞書順で最小になるようにしなければなりません。
例えば、入力が「abccb」であれば、出力は「abc」となります。

アルゴリズムの考え方

この問題は、貪欲法（グリーディ法）とスタックを組み合わせることで効率的に解くことができます。ポイントは次の2つです。

• 各文字が「今後まだ出現するか」を出現回数として管理すること
• すでにスタックに積んだ文字でも、後で再び出現できるなら、より小さい文字のために取り除けること

処理の手順

1. 答えを格納する空の文字列 ans を用意します。
2. 文字を一時的に保持するスタック st を定義します。
3. 各文字がスタック上に存在するかどうかを記録する、サイズ26の配列 onStack を用意します。
4. 各文字の残り出現回数を数えるためのマップ m を定義します。
5. n を文字列 s の長さとします。
6. まず、s の各文字の出現回数を m にカウントします。
7. 続いて、i = 0 から n - 1 までの各文字 x = s[i] に対して以下を行います。
   • m[x] を1減らします（この文字を1つ消費したことを記録）。
   • x がすでにスタック上にある場合（onStack[x - 'a'] が真）は、何もせず次の文字へ進みます。
   • スタックが空でなく、現在の文字 x がスタック最上位の文字より小さく、かつスタック最上位の文字が後でまた出現できる場合（m[st.top()] > 0）は、スタック最上位の文字を取り除きます。これにより、より小さい文字を前方に配置できます。
   • x をスタックにプッシュし、onStack[x - 'a'] を true にします。
8. 最後に、スタックが空になるまで文字を取り出して ans に連結し、ans を逆順にして返します。

入力例「abccb」での動作

• 'a' をプッシュ → スタック: [a]
• 'b' をプッシュ → スタック: [a, b]
• 'c' をプッシュ → スタック: [a, b, c]
• 2つ目の 'c' はすでにスタック上にあるためスキップ
• 2つ目の 'b' もすでにスタック上にあるためスキップ
• スタックから取り出すと「cba」になり、逆順にして「abc」を返します。

C++実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string ans = "";
        stack<char> st;
        vector<int> onStack(26);
        map<char, int> m;
        int n = s.size();

        // 各文字の出現回数をカウント
        for (int i = 0; i < n; i++) {
            m[s[i]]++;
        }

        for (int i = 0; i < n; i++) {
            char x = s[i];
            m[x]--;
            // すでにスタック上にあればスキップ
            if (onStack[x - 'a']) continue;
            // 後で再出現できる文字を取り除き、より小さい文字を優先
            while (!st.empty() && x < st.top() && m[st.top()]) {
                onStack[st.top() - 'a'] = false;
                st.pop();
            }
            st.push(x);
            onStack[x - 'a'] = true;
        }

        while (!st.empty()) {
            char x = st.top();
            st.pop();
            ans += x;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.removeDuplicateLetters("abccb");
    return 0;
}

入力

"abccb"

出力

"abc"

まとめ

本アルゴリズムでは、各文字は高々1回ずつしかプッシュ・ポップされないため、時間計算量は O(n) です。必要な補助領域もスタックとサイズ26の配列程度に収まるため、空間計算量も O(n) となります。スタックによる順序制御と出現回数カウントを組み合わせることで、重複の除去と辞書順最小化を同時に実現できる点が、この手法の大きな特徴です。