<p>You are given the string <code>croakOfFrogs</code>, which represents a combination of the string <code>&quot;croak&quot;</code> from different frogs, that is, multiple frogs can croak at the same time, so multiple <code>&quot;croak&quot;</code> are mixed.</p>

<p><em>Return the minimum number of </em>different<em> frogs to finish all the croaks in the given string.</em></p>

<p>A valid <code>&quot;croak&quot;</code> means a frog is printing five letters <code>&#39;c&#39;</code>, <code>&#39;r&#39;</code>, <code>&#39;o&#39;</code>, <code>&#39;a&#39;</code>, and <code>&#39;k&#39;</code> <strong>sequentially</strong>. The frogs have to print all five letters to finish a croak. If the given string is not a combination of a valid <code>&quot;croak&quot;</code> return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> croakOfFrogs = &quot;croakcroak&quot;
<strong>Output:</strong> 1 
<strong>Explanation:</strong> One frog yelling &quot;croak<strong>&quot;</strong> twice.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> croakOfFrogs = &quot;crcoakroak&quot;
<strong>Output:</strong> 2 
<strong>Explanation:</strong> The minimum number of frogs is two. 
The first frog could yell &quot;<strong>cr</strong>c<strong>oak</strong>roak&quot;.
The second frog could yell later &quot;cr<strong>c</strong>oak<strong>roak</strong>&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> croakOfFrogs = &quot;croakcrook&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> The given string is an invalid combination of &quot;croak<strong>&quot;</strong> from different frogs.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= croakOfFrogs.length &lt;= 10<sup>5</sup></code></li>
	<li><code>croakOfFrogs</code> is either <code>&#39;c&#39;</code>, <code>&#39;r&#39;</code>, <code>&#39;o&#39;</code>, <code>&#39;a&#39;</code>, or <code>&#39;k&#39;</code>.</li>
</ul>

class Solution {
    int valid(string s) {
        int n=s.size();
        vector<int>count(5,0);
        unordered_map<char,int>mpp;
        mpp['c']=0;
        mpp['r']=1;
        mpp['o']=2;
        mpp['a']=3;
        mpp['k']=4;
        for(int i=0;i<n;i++){
           char ch=s[i];
           int idx=mpp[ch];
           count[idx]++;
           int cnt=count[idx];
           for(int j=0;j<idx;j++){
            if(count[j]<cnt){
                return 0;
            }
           }
        }
        for(int i=1;i<5;i++){
            if(count[i]!=count[i-1]){
                return 0;
            }
        }
        return 1;
    }

public:
    int minNumberOfFrogs(string str) {
        int n = str.size();
        if(!valid(str)){
            return -1;
        }
        int ans = 0;
        int res = 0;
        for(int i=0;i<n;i++){
            if(str[i]=='c'){
                ans++;
            }
            else if(str[i]=='k'){
                ans--;
            }
            res=max(res,ans);
        }
    //     vector<int> a;
    //     vector<int> d;
    //     for (int i = 0; i < n; i++) {
    //         if (valid(i, str) == -1) {
    //             return -1;
    //         }
    //         if (str[i] == 'c') {
    //             int dep = valid(i, str);
    //             a.push_back(i);
    //             d.push_back(dep);
    //         }
    //     }
    //     sort(a.begin(), a.end());
    //     sort(d.begin(), d.end());
    //     int n1 = a.size();
    //     int j1 = 0;
    //     int j2 = 0;
    //     while (j1 < n1) {
    //         if (a[j1] <= d[j2]) {
    //             ans++;
    //             j1++;
    //         } else {
    //             ans--;
    //             j2++;
    //         }
    //         res = max(res, ans);
    //     }
        return res;
    }
};
12700