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 croak in the given string.
A valid "croak" means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of 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.

Example 4:
Input: croakOfFrogs = "croakcroa"
Output: -1

 
Constraints:

1 <= croakOfFrogs.length <= 10^5
All characters in the string are: 'c', 'r', 'o', 'a' or 'k'.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Mathematics

Starter code: class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        

Solutions:
class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		if len(croakOfFrogs) % 5 != 0 or croakOfFrogs[0] != 'c' or croakOfFrogs[-1] != 'k':
			return -1
		letters = {'c': 0, 'r': 0, 'o': 0, 'a': 0, 'k': 0}
		frogs = 0
		temp = 0
		for l in croakOfFrogs:
			letters[l] += 1
			temp = letters['c'] - letters['k']
			if temp > frogs:
				frogs = temp
		c_count = letters['c']
		for letter in letters:
			if letters[letter] != c_count:
				return -1
		return frogs


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		croaks = {'c': [], 'r': [], 'o': [], 'a': []}
		nfrogs = 0
		icroak = 0
		curfrogs = 0
		for sound in croakOfFrogs:
			if sound == 'c':
				icroak += 1
				croaks['c'].append(icroak)
				curfrogs += 1
				nfrogs = max(curfrogs, nfrogs)
			elif sound == 'r':
				if croaks['c']:
					croaks['r'].append(croaks['c'].pop())
				else:
					return -1
			elif sound == 'o':
				if croaks['r']:
					croaks['o'].append(croaks['r'].pop())
				else:
					return -1
			elif sound == 'a':
				if croaks['o']:
					croaks['a'].append(croaks['o'].pop())
				else:
					return -1
			elif sound == 'k':
				if croaks['a']:
					croaks['a'].pop()
					curfrogs -= 1
				else:
					return -1
			else:
				return -1
		for sound in croaks:
			if croaks[sound] != []:
				return -1
		return nfrogs


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		ans = 1
		waitingFor = defaultdict(int)
		croak = 'croak'
		croakDict = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4}
		for char in croakOfFrogs:
			if char == 'c':
				if waitingFor[char] != 0 and ans <= waitingFor[char]:
					ans += 1
				waitingFor[char] += 1
				waitingFor[croak[croakDict[char] + 1]] += 1
			else:
				if waitingFor[char] == 0:
					return -1
				waitingFor[char] -= 1
				if char != 'k':
					waitingFor[croak[croakDict[char] + 1]] += 1
				else:
					waitingFor['c'] -= 1
		for char in waitingFor:
			if waitingFor[char] != 0:
				return -1
		return ans


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		if len(croakOfFrogs) % 5 != 0 or croakOfFrogs[0] != 'c' or croakOfFrogs[-1] != 'k':
			return -1
		max_frog_croak = 0
		present_frog_croak = 0
		d = {}
		d['c'] = 0
		d['r'] = 0
		d['o'] = 0
		d['a'] = 0
		d['k'] = 0
		for ch in croakOfFrogs:
			d[ch] += 1
			if ch == 'c':
				present_frog_croak += 1
			if ch == 'k':
				present_frog_croak -= 1
			max_frog_croak = max(max_frog_croak, present_frog_croak)
		if d['c'] != d['r'] or d['r'] != d['o'] or d['o'] != d['a'] or (d['a'] != d['k']):
			return -1
		return max_frog_croak


class Solution:

	def minNumberOfFrogs(self, croak: str) -> int:
		if len(croak) == 0:
			return 0
		if croak[0] != 'c':
			return -1
		if len(croak) % 5 != 0:
			return -1
		arr = [0 for _ in range(6)]
		arr[0] = 9999999
		index = {'c': 1, 'r': 2, 'o': 3, 'a': 4, 'k': 5}
		for letter in croak:
			i = index[letter]
			if arr[i - 1] > 0:
				if i == 1 and arr[5]:
					arr[5] -= 1
				arr[i - 1] -= 1
				arr[i] += 1
			else:
				return -1
		for i in arr[1:-1]:
			if i != 0:
				return -1
		return arr[-1]


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		(chr_c, chr_r, chr_o, chr_a) = (0, 0, 0, 0)
		count = 0
		for s in croakOfFrogs:
			if s == 'c':
				chr_c += 1
			elif s == 'r':
				if chr_c <= 0:
					return -1
				chr_c -= 1
				chr_r += 1
			elif s == 'o':
				if chr_r <= 0:
					return -1
				chr_r -= 1
				chr_o += 1
			elif s == 'a':
				if chr_o <= 0:
					return -1
				chr_o -= 1
				chr_a += 1
			else:
				if chr_a <= 0:
					return -1
				chr_a -= 1
			count = max(count, chr_c + chr_r + chr_o + chr_a)
		if chr_c + chr_r + chr_o + chr_a > 0:
			return -1
		return count


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		curr = 0
		maxcurr = 0
		c = r = o = a = k = 0
		for i in croakOfFrogs:
			if i == 'c':
				c += 1
				curr += 1
			elif i == 'r':
				r += 1
			elif i == 'o':
				o += 1
			elif i == 'a':
				a += 1
			else:
				k += 1
				curr -= 1
			maxcurr = max(curr, maxcurr)
			if c < r or r < o or o < a or (a < k):
				return -1
		if curr == 0 and c == r and (r == o) and (o == a) and (a == k):
			return maxcurr
		return -1


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		neighcount = [0, 0, 0, 0, 0]
		minhorses = 0
		nstarted = 0
		nended = 0
		for s in croakOfFrogs:
			if s == 'c':
				neighcount[0] += 1
				nstarted += 1
			elif s == 'r':
				neighcount[1] += 1
				neighcount[0] -= 1
			elif s == 'o':
				neighcount[2] += 1
				neighcount[1] -= 1
			elif s == 'a':
				neighcount[3] += 1
				neighcount[2] -= 1
			elif s == 'k':
				neighcount[4] += 1
				neighcount[3] -= 1
				nstarted -= 1
			else:
				return -1
			if nstarted > minhorses:
				minhorses = nstarted
			if neighcount[0] < 0 or neighcount[1] < 0 or neighcount[2] < 0 or (neighcount[3] < 0):
				return -1
		if neighcount[0] == 0 and neighcount[1] == 0 and (neighcount[2] == 0) and (neighcount[3] == 0):
			return minhorses
		else:
			return -1


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		if not len(croakOfFrogs):
			return 0
		c = 0
		r = 0
		o = 0
		a = 0
		k = 0
		count = 0
		for ch in croakOfFrogs:
			if ch == 'c':
				count += 1
				c += 1
			elif ch == 'r':
				if not c:
					return -1
				c -= 1
				r += 1
			elif ch == 'o':
				if not r:
					return -1
				r -= 1
				o += 1
			elif ch == 'a':
				if not o:
					return -1
				o -= 1
				a += 1
			elif ch == 'k':
				if not a:
					return -1
				a -= 1
				k = max(k, count)
				count -= 1
			else:
				return -1
		if not c and (not r) and (not o) and (not a):
			return k
		else:
			return -1


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		if len(croakOfFrogs) % 5 > 0:
			return -1
		pos = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4}
		count = [0] * 5
		res = 1
		for c in croakOfFrogs:
			count[pos[c]] += 1
			if pos[c] > 0:
				if count[pos[c]] > count[pos[c] - 1]:
					return -1
			if pos[c] == 4:
				for i in range(5):
					count[i] -= 1
			elif pos[c] == 0:
				res = max(res, count[0])
		for i in range(4):
			if count[i + 1] != count[i]:
				return -1
		return res


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		(frogs, d) = ([], {c: [] for c in 'croak'})
		for c in croakOfFrogs:
			bucket = 'croak'['croak'.find(c) - 1]
			if not d[bucket]:
				if bucket != 'k':
					return -1
				frogs.append([])
				d[c].append(len(frogs) - 1)
			else:
				d[c].append(d[bucket].pop())
				if c == 'c':
					frogs[d[c][-1]].clear()
			frogs[d[c][-1]].append(c)
		return len(frogs) if all((len(frog) == 5 for frog in frogs)) else -1


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		r = 0
		o = 0
		a = 0
		k = 0
		frogs = 0
		max_frogs = 0
		for L in croakOfFrogs:
			if L == 'c':
				frogs += 1
				max_frogs = max(max_frogs, frogs)
				r += 1
			elif L == 'r':
				if r == 0:
					return -1
				else:
					r -= 1
					o += 1
			elif L == 'o':
				if o == 0:
					return -1
				else:
					o -= 1
					a += 1
			elif L == 'a':
				if a == 0:
					return -1
				else:
					a -= 1
					k += 1
			elif k == 0:
				return -1
			else:
				k -= 1
				frogs -= 1
		if r + o + a + k != 0:
			return -1
		return max_frogs


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		if len(croakOfFrogs) % 5 != 0:
			return -1
		min_val = 0
		cnt = {char: 0 for char in 'croak'}
		for char in croakOfFrogs:
			if char not in 'croak' or not cnt['c'] >= cnt['r'] >= cnt['o'] >= cnt['a'] >= cnt['k']:
				return -1
			cnt[char] += 1
			min_val = max(min_val, cnt['c'] - cnt['k'])
		return min_val if cnt['c'] == cnt['r'] == cnt['o'] == cnt['a'] == cnt['k'] else -1


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		if len(croakOfFrogs) % 5 != 0:
			return -1
		nums = [0] * 5
		dic = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4}
		res = 1
		for ch in croakOfFrogs:
			if dic[ch] != 0 and nums[dic[ch]] >= nums[dic[ch] - 1]:
				return -1
			nums[dic[ch]] += 1
			res = max(res, nums[0])
			if ch == 'k':
				for i in range(5):
					nums[i] -= 1
		return res


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		(c, r, o, a, k, in_use, answer) = (0, 0, 0, 0, 0, 0, 0)
		for d in croakOfFrogs:
			if d == 'c':
				(c, in_use) = (c + 1, in_use + 1)
			elif d == 'r':
				r += 1
			elif d == 'o':
				o += 1
			elif d == 'a':
				a += 1
			else:
				(k, in_use) = (k + 1, in_use - 1)
			answer = max(answer, in_use)
			if c < r or r < o or o < a or (a < k):
				return -1
		if in_use == 0 and c == r and (r == o) and (o == a) and (a == k):
			return answer
		return -1


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		arr = [0] * 5
		for item in croakOfFrogs:
			if item == 'c':
				arr[0] += 1
			elif item == 'r':
				arr[1] += 1
				for i in range(0, 1):
					if arr[i] < arr[1]:
						return -1
			elif item == 'o':
				arr[2] += 1
				for i in range(0, 1):
					if arr[i] < arr[2]:
						return -1
			elif item == 'a':
				arr[3] += 1
				for i in range(0, 1):
					if arr[i] < arr[3]:
						return -1
			else:
				arr[4] += 1
				for i in range(0, 1):
					if arr[i] < arr[4]:
						return -1
		cur = arr[0]
		for i in range(1, 5):
			if arr[i] != cur:
				return -1
		cur_frogs = 0
		result = float('-inf')
		p = 0
		while p < len(croakOfFrogs):
			if croakOfFrogs[p] == 'c':
				cur_frogs += 1
			elif croakOfFrogs[p] == 'k':
				cur_frogs -= 1
			result = max(cur_frogs, result)
			p += 1
		return result


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		dic = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4}
		num = 0
		num_c = 0
		num_k = 0
		freq = [0] * 5
		if not croakOfFrogs[0] == 'c':
			return -1
		for ch in croakOfFrogs:
			if 'c' == ch:
				if num_k == 0:
					num_c += 1
				else:
					num_k -= 1
				num = max(num_c, num)
			if 'k' == ch:
				num_k += 1
		for ch in croakOfFrogs:
			freq[dic[ch]] += 1
			for idx in range(1, 5):
				if freq[idx] > freq[idx - 1]:
					return -1
		for idx in range(1, 5):
			if not freq[idx] == freq[idx - 1]:
				return -1
		return num


class Solution:

	def minNumberOfFrogs(self, s: str) -> int:
		rec = defaultdict(int)
		count = 0
		if not s.startswith('c') or not s.endswith('k'):
			return -1
		for i in range(len(s)):
			if rec['c'] >= rec['r'] >= rec['o'] >= rec['a'] >= rec['k']:
				rec[s[i]] += 1
				if count < rec['c']:
					count += 1
				if s[i] == 'k':
					for k in rec:
						rec[k] -= 1
			else:
				return -1
		return count


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		croak = 'croak'
		frogs = 0
		openCroaks = list()
		char2count = {'c': 0, 'r': 0, 'o': 0, 'a': 0, 'k': 0}
		for char in croakOfFrogs:
			if char not in croak:
				return -1
			if char == 'c':
				char2count[char] += 1
			elif char2count[croak[croak.find(char) - 1]] > 0:
				char2count[croak[croak.find(char) - 1]] -= 1
				if char != 'k':
					char2count[char] += 1
			else:
				return -1
			frogs = max(frogs, sum(char2count.values()))
		return frogs if sum(char2count.values()) == 0 else -1


chars = ['c', 'r', 'o', 'a', 'k']
C = len(chars)
cs = set(chars)

class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		N = len(croakOfFrogs)
		if N == 0:
			return 0
		if N % 5 != 0:
			return -1
		counter = Counter(croakOfFrogs)
		if len(counter) != 5:
			return -1
		totFreq = None
		for c in counter:
			if not totFreq:
				totFreq == counter[c]
			elif totFreq != counter[c]:
				return -1
		dic = [0] * C
		ans = 0
		for i in range(N):
			c = croakOfFrogs[i]
			if c not in cs:
				return -1
			if c == chars[0]:
				for j in range(1, len(chars)):
					dic[j] += 1
				ans = max(ans, dic[C - 1])
			else:
				j = chars.index(c)
				dic[j] -= 1
				prev = dic[j]
				for k in range(j - 1, -1, -1):
					if dic[k] > prev:
						return -1
					prev = dic[k]
		return ans


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		if len(croakOfFrogs) % 5 != 0:
			return -1
		dic = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4}
		numsCount = [0] * 5
		max_val = numOfFrogs = 0
		for i in range(len(croakOfFrogs)):
			if croakOfFrogs[i] == 'c':
				numOfFrogs += 1
			if croakOfFrogs[i] == 'k':
				numOfFrogs -= 1
			max_val = max(numOfFrogs, max_val)
			numsCount[dic[croakOfFrogs[i]]] += 1
			for j in range(0, 4):
				if numsCount[j] < numsCount[j + 1]:
					return -1
		return max_val


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		frog_counter = 0
		crk_dict = {'c': 0, 'r': 0, 'o': 0, 'a': 0, 'k': 0}
		if croakOfFrogs[0] != 'c':
			return -1
		elif croakOfFrogs[-1] != 'k':
			return -1
		else:
			for i in range(len(croakOfFrogs)):
				if crk_dict['c'] >= crk_dict['r'] >= crk_dict['o'] >= crk_dict['a'] >= crk_dict['k']:
					crk_dict[croakOfFrogs[i]] += 1
					if frog_counter < crk_dict['c']:
						frog_counter += 1
					if croakOfFrogs[i] == 'k':
						for m in crk_dict:
							crk_dict[m] -= 1
				else:
					return -1
			return frog_counter


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		croak = 'croak'
		croak_positions = {char: 0 for char in croak}
		max_size = 0
		completed = 0
		for char in croakOfFrogs:
			if char in croak_positions:
				croak_positions[char] += 1
			else:
				return -1
			for (char, count) in croak_positions.items():
				if char != croak[0]:
					diff = croak_positions[croak[0]] - count
					if diff < 0:
						return -1
					if diff > max_size:
						max_size = diff
		for (char, count) in croak_positions.items():
			if count != croak_positions[croak[0]]:
				return -1
		return max_size


class Solution:

	def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
		res = croaking = c = r = o = a = k = 0
		for x in croakOfFrogs:
			if x == 'c':
				(c, croaking) = (c + 1, croaking + 1)
				res = max(res, croaking)
			elif x == 'r':
				r += 1
			elif x == 'o':
				o += 1
			elif x == 'a':
				a += 1
			else:
				(k, croaking) = (k + 1, croaking - 1)
			if c < r or r < o or o < a or (a < k):
				return -1
		return res if c == r == o == a == k and croaking == 0 else -1