Connection Status:
Competition Arena > Quacking

Quacking

SRM 687 · 2016-04-01 · by lg5293

SRM 687 · 2016-04-01 · by lg5293 · Greedy
Class Name: Quacking
Return Type: int
Method Name: quack
Arg Types: (string)
Problem Statement

Problem Statement

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.

Constraints

  • s will have between 5 and 2,500 characters, inclusive.
  • Each character of s will be 'q', 'u', 'a', 'c', or 'k'.
Examples
0)
"quqacukqauackck"
Returns: 2

This is the same as the one from the problem statement.

1)
"kcauq"
Returns: -1

A backward duck is not a real duck.

2)
"quackquackquackquackquackquackquackquackquackquack"
Returns: 1

A single duck can make arbitrarily many quack sounds.

3)
"qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk"
Returns: 10
4)
"quqaquuacakcqckkuaquckqauckack"
Returns: 3

This is one possible solution with 3 ducks. Mixed: quqaquuacakcqckkuaquckqauckack Duck1: ____q_u__a___ck_______________ Duck2: __q__u_ac_k_q___ua__ckq_u__ack Duck3: qu_a_______c___k__qu___a_ck___ Here, we can verify that each letter comes from exactly one duck.

5)
"quackqauckquack"
Returns: -1

Note that the second quack is misspelled.

73)
"ackquackqu"
Returns: -1

This is not a valid recording of ducks. In a valid recording, each duck makes one or more complete quacks, it does not start in the middle of a quack.

Submissions are judged against all 105 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Quacking with a public method int quack(string s) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous