[TopCoder]SRM 687 Div2 Quacking | 书影博客
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.
Read full article from [TopCoder]SRM 687 Div2 Quacking | 书影博客
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.
遍历字符串s，记当前字符为c，字符c在"quack"中的位置对应的字典为QUACK。
利用数组duck记录当前已经叫出"q", "u", "a", "c", "k"对应下标i的鸭子个数。
如果某时刻duck[i - 1]为0，则说明当前序列不合法。
某一时刻"q", "u", "a", "c"对应的鸭子数目之和即为当前时刻的最小鸭子个数。
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"对应的鸭子数目之和即为当前时刻的最小鸭子个数。
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 ansRead full article from [TopCoder]SRM 687 Div2 Quacking | 书影博客
