文字列kの距離をC++で並べ替える

したがって、入力がs ="aabbcc"、k =3の場合、同じ文字が少なくとも互いに3の距離にあるため、出力は"abcabc"になります。

これを解決するには、次の手順に従います-

• ret：=空の文字列

• 1つのマップを定義するm

• n：=sのサイズ

• 初期化i：=0の場合、i

  • （m [s [i]]を1増やします）

• 1つの優先キューpqを定義する

• キーと値のペアごとに、mでそれを実行します-

  • temp：=キーとその値のペア

  • 温度をpqに挿入

  • （1つ増やします）

• 1つのdequedqを定義する

• （pqが空ではない）間、-

  • curr：=pqの先頭

  • pqから要素を削除する

  • ret：=ret + curr.first

  • （curr.secondを1減らします）

  • dqの最後にcurrを挿入します

  • dqのサイズ>=kの場合、-

    • curr：=dqの最初の要素

    • dqからフロント要素を削除します

    • curr.second> 0の場合、-

      • currをpqに挿入します

• （dqが空ではなく、dqの最初の要素が0と同じである場合）、do −

  • dqからフロント要素を削除します

• return（dqが空の場合は、ret、それ以外の場合は空白の文字列）

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
struct Comparator {
   bool operator()(pair<char, int> a, pair<char, int> b) {
      return !(a.second > b.second);
   }
};
class Solution {
public:
   string rearrangeString(string s, int k) {
      string ret = "";
      unordered_map<char, int> m;
      int n = s.size();
      for (int i = 0; i < n; i++) {
         m[s[i]]++;
      }
      unordered_map<char, int>::iterator it = m.begin();
      priority_queue<pair<char, int<, vector<pair<char, int>>,
      Comparator> pq;
      while (it != m.end()) {
         pair<char, int> temp = {it->first, it->second};
         pq.push(temp);
         it++;
      }
      deque<pair<char, int>> dq;
      while (!pq.empty()) {
         pair<char, int> curr = pq.top();
         pq.pop();
         ret += curr.first;
         curr.second--;
         dq.push_back(curr);
         // cout << ret << " " << dq.size() << endl;
         if (dq.size() >= k) {
            curr = dq.front();
            dq.pop_front();
            if (curr.second > 0)
            pq.push(curr);
         }
      }
      while (!dq.empty() && dq.front().second == 0)
         dq.pop_front();
      return dq.empty() ? ret : "";
   }
};
main() {
   Solution ob;
   cout << (ob.rearrangeString("aabbcc", 3));
}

入力

"aabbcc", 3

出力

bacbac