C++で鳴くカエルの最小数

croakOfFrogsという文字列があるとします。これは、さまざまなカエルの文字列「croak」の組み合わせを表します。複数のカエルが同時に鳴く可能性があるため、複数の「croak」が混在しています。与えられた弦のすべての鳴き声を仕上げるには、さまざまなカエルの最小数を見つける必要があります。

ここで有効な「鳴き声」とは、カエルが5文字の「c」、「r」、「o」、「a」、「k」を順番に生成していることを意味します。カエルは、鳴き声を完成させるために5文字すべてを生成する必要があります。文字列が有効な「クローク」文字列でない場合は、-1を返します。

したがって、入力が「crcoakroak」のような場合、最初のカエルが「crcoakroak」と叫ぶ可能性があるため、出力は2になります。 2番目のカエルは後で「crcoakroak」と叫ぶ可能性があります。

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

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

• サイズの配列chを定義します：5 {'c'、'r'、'o'、'a'、'k'}

  で割り当てます

• temp：=0、ret：=0

• sの各要素cについて、実行します

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

  • maxVal：=m [ch [0]]

  • 初期化i：=0の場合、i <5の場合、更新（iを1増やします）、実行-

    • maxVal

      • -1を返す

    • maxVal：=m [ch [i]]

  • cが'c'と同じ場合、-

    • （温度を1上げます）

  • それ以外の場合、cが'k'と同じである場合、-

    • （温度を1下げます）

  • ret：=retとtempの最大値

• 初期化i：=1の場合、i <5の場合、更新（iを1増やします）、実行-

  • m[ch[0]]がm[ch[i]]と等しくない場合、-

    • -1を返す

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minNumberOfFrogs(string s) {
      map<char, int> m;
      char ch[5] = { 'c', 'r', 'o', 'a', 'k' };
      int temp = 0;
      int ret = 0;
      for (auto& c : s) {
         m[c]++;
         int maxVal = m[ch[0]];
         for (int i = 0; i < 5; i++) {
            if (maxVal < m[ch[i]] || m[ch[i]] < 0) {
               return -1;
            }
            maxVal = m[ch[i]];
         }
         if (c == 'c') {
            temp++;
         }
         else if (c == 'k') {
            temp--;
         }
         ret = max(ret, temp);
      }
      for (int i = 1; i < 5; i++) {
         if (m[ch[0]] != m[ch[i]])
            return -1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minNumberOfFrogs("crcoakroak"));
}

入力

"crcoakroak"

出力

2