Bigger is Greater


これは、辞書の順序で現在の文字列の後の文字列を求める問題です.
解題ポリシー
次の文字列を辞書順に検索するアルゴリズムは、次のとおりです.
  • の一番後ろから次の条件を満たす文字を探します.
    1.1. 現在の字の後の字の中で、現在の字より大きい最小の字を探します.
  • で検索された文字と現在の文字の位置が入れ替わる.
  • の前から現在までの文字はそのまま使用されており、後ろの部分を並べ替えて貼り付けています.
  • 1.1条件を満たす文字がなければ、答えがないことを返します.

    リファレンス
    https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
  • 以上の手順をコードで実現した部分が注釈部分となる.
    より簡便に解くためにnext置換を用いることができる.
    next permutationは、現在の文字列以来初めて発生したシーケンスを返すすべてのシーケンスを検索する関数です.
    コード#コード#
    string biggerIsGreater(string w) {
        int cnt = 0;
        do{
            if(cnt == 1)
                return w;
            cnt++;
        }while(next_permutation(w.begin(), w.end()));
        return "no answer";
        
        // for(int i=w.size()-2;i>=0;i--){
        //     int idx = -1;
        //     for(int j=w.size()-1;j>i;j--){
        //         if(w[j] > w[i]){
        //             if(idx == -1)
        //                 idx = j;
        //             else{
        //                 if(w[j] < w[idx])
        //                     idx = j;
        //             }
        //         }
        //     }
        //     if(idx == -1)
        //         continue;
        //     string ans = "";
        //     char tmp = w[idx];
        //     w[idx] = w[i];
        //     w[i] = tmp;
        //     vector<char> v;
        //     for(int j=0;j<w.size();j++){
        //         if(j <= i){
        //             ans += w[j];
        //         }else{
        //             v.push_back(w[j]);
        //         }
        //     }
        //     sort(v.begin(), v.end());
        //     for(int j=0;j<v.size();j++){
        //         ans += v[j];
        //     }
        //     return ans;
        // }
        // return "no answer";
    }
    ソース
    https://www.hackerrank.com/challenges/bigger-is-greater/problem