题目描述：
Ducks have started mysteriously appearing in your room. All ducks make the same sound: "quack". Each duck makes the sound one or more times, one after another. For example, valid sounds for a single duck are "quack", "quackquackquackquack", "quackquack", etc.
You have lost count of how many ducks are in your room. The ducks are quacking, and the sounds of their quacks are getting mixed up. You have recorded the sounds, obtaining a string of characters. When you later listened to the recording, you realized that the quacking of each individual duck forms a (not necessarily contiguous) subsequence of the recording. You also noticed that each letter in the recording belongs to exactly one duck. For example, if there were two ducks, you may have recorded "quqacukqauackck".
You are given a string s that contains an arbitrary recording. Find and return the smallest number of ducks that could have produced the recording. Note that it is possible that the given recording is not a valid recording of quacking ducks. In such case, return -1.
题目大意：
你的房间里不知怎么出现了一些鸭子。所有的鸭子都发出同样的声音："嘎(quack)"。每只鸭子叫一次或者多次，叫声此起彼伏。例如，一只单独的鸭子的有效的声音序列是"quack", "quackquackquackquack"，"quackquack"，等等。
你已经无法分辨房间里到底有多少只鸭子了。鸭子的叫声混杂在一起。你对声音做了记录，得到一个字符串。之后当你回放这些记录时，你意识到每一只鸭子各自的叫声构成了记录的（不一定是邻接的）一个子序列。你也注意到记录中的每一个字母都只属于唯一的一只鸭子。例如，如果有两只鸭子，其叫声可能为"quqacukqauackck"。
给定一个包含任意记录的字符串s。寻找并返回可能形成此序列的鸭子数目的最小值。请注意字符串有可能不是一个有效的叫声序列。此时返回-1。
解题思路：
遍历字符串s，记当前字符为c，字符c在"quack"中的位置对应的字典为QUACK。
利用数组duck记录当前已经叫出"q", "u", "a", "c", "k"对应下标i的鸭子个数。
如果某时刻duck[i - 1]为0，则说明当前序列不合法。
某一时刻"q", "u", "a", "c"对应的鸭子数目之和即为当前时刻的最小鸭子个数。
Python代码：
class Quacking(object):
def quack(self, s):
QUACK = {v : i + 1 for i, v in enumerate('quack')}
size = len(s)
duck = [0] * 6
ans = cur = 0
for c in s:
i = QUACK[c]
if i > 1 and duck[i - 1] == 0:
return -1
duck[i - 1] -= 1
duck[i] += 1
if i == 1: cur += 1
elif i == 5: cur -= 1
ans = max(cur, ans)
if size % 5 or cur:
return -1
return ans
比赛时的解题思路：
遍历字符串s，记当前字符为c，字符c在"quack"中的位置对应的前缀为prefix。
利用字典duck记录当前已经叫出"q", "qu", "qua", "quac", "quack"的鸭子个数。
如果某时刻prefix的数目为0，则说明当前序列不合法。
某一时刻"q", "qu", "qua", "quac"对应的鸭子数目之和即为当前时刻的最小鸭子个数。
Python代码：
class Quacking(object):
def quack(self, s):
QUACK = 'quack'
size = len(s)
duck = {QUACK[:i] : 0 for i in range(size + 1)}
ans = 0
for c in s:
for i, p in enumerate(QUACK):
if p == c:
prefix = QUACK[:i]
if len(prefix) and duck[prefix] == 0:
return -1
duck[prefix] -= 1
duck[prefix + p] += 1
break
ans = max(sum(duck.values()) - duck[''] - duck[QUACK], ans)
if size % 5 or duck[QUACK] != size / 5:
return -1
return ans
本文链接：http://bookshadow.com/weblog/2016/04/07/topcoder-srm-687-div2-quacking/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
