Question

1419. Minimum Number of Frogs Croaking

中文文档

Description

You are given the string croakOfFrogs, which represents a combination of the string "croak" from different frogs, that is, multiple frogs can croak at the same time, so multiple "croak" are mixed.

_Return the minimum number of _different_ frogs to finish all the croaks in the given string._

A valid "croak" means a frog is printing five letters 'c', 'r', 'o', 'a', and 'k' sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of a valid "croak" return -1.

 

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1 
Explanation: One frog yelling "croak" twice.

Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2 
Explanation: The minimum number of frogs is two. 
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".

Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.

 

Constraints:

• 1 <= croakOfFrogs.length <= 105
• croakOfFrogs is either 'c', 'r', 'o', 'a', or 'k'.

Solutions

Solution 1

class Solution:
  def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
    if len(croakOfFrogs) % 5 != 0:
      return -1
    idx = {c: i for i, c in enumerate('croak')}
    cnt = [0] * 5
    ans = x = 0
    for i in map(idx.get, croakOfFrogs):
      cnt[i] += 1
      if i == 0:
        x += 1
        ans = max(ans, x)
      else:
        if cnt[i - 1] == 0:
          return -1
        cnt[i - 1] -= 1
        if i == 4:
          x -= 1
    return -1 if x else ans

class Solution {
  public int minNumberOfFrogs(String croakOfFrogs) {
    int n = croakOfFrogs.length();
    if (n % 5 != 0) {
      return -1;
    }
    int[] idx = new int[26];
    String s = "croak";
    for (int i = 0; i < 5; ++i) {
      idx[s.charAt(i) - 'a'] = i;
    }
    int[] cnt = new int[5];
    int ans = 0, x = 0;
    for (int k = 0; k < n; ++k) {
      int i = idx[croakOfFrogs.charAt(k) - 'a'];
      ++cnt[i];
      if (i == 0) {
        ans = Math.max(ans, ++x);
      } else {
        if (--cnt[i - 1] < 0) {
          return -1;
        }
        if (i == 4) {
          --x;
        }
      }
    }
    return x > 0 ? -1 : ans;
  }
}

class Solution {
public:
  int minNumberOfFrogs(string croakOfFrogs) {
    int n = croakOfFrogs.size();
    if (n % 5 != 0) {
      return -1;
    }
    int idx[26]{};
    string s = "croak";
    for (int i = 0; i < 5; ++i) {
      idx[s[i] - 'a'] = i;
    }
    int cnt[5]{};
    int ans = 0, x = 0;
    for (char& c : croakOfFrogs) {
      int i = idx[c - 'a'];
      ++cnt[i];
      if (i == 0) {
        ans = max(ans, ++x);
      } else {
        if (--cnt[i - 1] < 0) {
          return -1;
        }
        if (i == 4) {
          --x;
        }
      }
    }
    return x > 0 ? -1 : ans;
  }
};

func minNumberOfFrogs(croakOfFrogs string) int {
  n := len(croakOfFrogs)
  if n%5 != 0 {
    return -1
  }
  idx := [26]int{}
  for i, c := range "croak" {
    idx[c-'a'] = i
  }
  cnt := [5]int{}
  ans, x := 0, 0
  for _, c := range croakOfFrogs {
    i := idx[c-'a']
    cnt[i]++
    if i == 0 {
      x++
      ans = max(ans, x)
    } else {
      cnt[i-1]--
      if cnt[i-1] < 0 {
        return -1
      }
      if i == 4 {
        x--
      }
    }
  }
  if x > 0 {
    return -1
  }
  return ans
}

function minNumberOfFrogs(croakOfFrogs: string): number {
  const n = croakOfFrogs.length;
  if (n % 5 !== 0) {
    return -1;
  }
  const idx = (c: string): number => 'croak'.indexOf(c);
  const cnt: number[] = [0, 0, 0, 0, 0];
  let ans = 0;
  let x = 0;
  for (const c of croakOfFrogs) {
    const i = idx(c);
    ++cnt[i];
    if (i === 0) {
      ans = Math.max(ans, ++x);
    } else {
      if (--cnt[i - 1] < 0) {
        return -1;
      }
      if (i === 4) {
        --x;
      }
    }
  }
  return x > 0 ? -1 : ans;
}