C++のパーティションラベル

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

• cntと呼ばれる1つのマップを定義します
• 0からsの範囲のiの場合、cnt [s [i]]：=i
• j：=0、start：=0およびi：=0およびn：=sのサイズ
• 1つの配列を定義します
• while i
• j：=jとcntの最大値[s[i]]
• i =jの場合、i – start + 1をansに挿入し、start：=i + 1
• iを1増やします

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> partitionLabels(string s) {
      map <char, int> cnt;
      for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
      int j = 0, start = 0;
      int i = 0;
      int n = s.size();
      vector <int> ans;
      while(i < n){
         j = max(j, cnt[s[i]]);
         if( i == j){
            ans.push_back(i-start+ 1);
            start = i + 1;
         }
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
}

入力

"ababcbacadefegdehijhklij"

出力

[9,7,8]