题目
解法:
这个题目有点意思的,比较巧妙。
我们需要找的是,这五个字母在某个时间出现的最大次数。限制条件是,每当遇到一个k的时候,放掉一只青蛙。同时需要检查给的字符串是不是无效,依照两个规则判断:
- 如果出现了一个字符,但是应该出现在他之前的字符没有出现,比如直接来个r,那就无效
- 当所有过程结束,所有的字符应该要刚好形成完整的若干个croak
接下来的就是实现问题了
class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
# main idea: keep the appeared time of every char, we only need to find the maximum appeared time of one char in 'croak'. When 'k' encountered, meaning one croak finish, so we decrease the appeared time for all other chars by 1 (same as release one frog)
# two situations for return -1: 1. if a char appeared, but the char supposed to appear before current does not exist, it's invalid 2. when finish, not all the char participated in forming a complete croak
char2ind = {'c':1,'r':2,'o':3,'a':4,'k':5}
# a list save the appeared times of every char
char_appeared = [0]*6
# make the first to be 1 for the situation when we encouter 'c'
char_appeared[0] = 1
min_frog = 0
for c in croakOfFrogs:
ind = char2ind[c]
# if the previous one not exist, it's invalid
if not char_appeared[ind-1]:
return -1
char_appeared[ind] += 1
min_frog = max(min_frog,char_appeared[ind])
# once 'k' appear, means we can free 1 frog
if c == 'k':
for i in range(1,6):
char_appeared[i] -= 1
# if all the chars can not form several complete 'croak'
for i in range(1,6):
if char_appeared[i]:
return -1
return min_frog