### Leetcode #1419: Minimum Number of Frogs Croaking

Minimum Number of Frogs Croaking

#### Thought Process

If we have the information about the number of frogs that are croaking simultaneously at any given time, it is not difficult to figure out that the number of distinct frogs that we must have is equal to the maximum number of frogs croaking simultaneously over a period. For example, say at t=0, t=1, and t=2, the number of frogs that are croaking is 1, 2, and 1 respectively. This tells us that, we must have at least 2 frogs for the above scenario to be valid.

Now, finding how many frogs are croaking at any time is also not difficult. We know that each “croaking” starts with a ‘c’ and ends with a ‘k’. Initially, 0 frogs are croaking. So whenever we hear a ‘c’, we will increment the count of frogs that are croaking by 1. Similarly, for every ‘k’ we will reduce it by 1.

#### Algorithm

1. Initially, the number of croaking frogs is 0.
2. For every character in the croaking sequence –
1. Keep a track of how many times each character has been seen.
2. Make sure that the sequence is still valid.
3. If the character is ‘c’, a frog has started to croak. So increment the frogs’ count and vice versa for ‘k’.
4. Find the max number of frogs croaking simultaneously.

#### Code

 class Solution { unordered_map frequency; // Stores how many times each sound has occured. // Sounds are c, r, o, a, k. /* * At any time, for a sequence to be valid, number of 'c' must not be less than 'r'. * Similarly, #'r' shouldn't less than #'o', and so on. */ bool isStateValid() { return (frequency['c'] >= frequency['r']) && (frequency['r'] >= frequency['o']) && (frequency['o'] >= frequency['a']) && (frequency['a'] >= frequency['k']); } public: /* * Minimum number of frogs that we need is maximum number of frogs that are * croaking simultaneously. * Each "croaking" is a sequence of c, r, o, a, and k. * Sound is a character in croakSequence. */ int minNumberOfFrogs(string croakSequence) { int numCroakingFrogs = 0; // Number of distinct frogs that are croaking at // any given time. int answer = 0; // Hold the final answer. for (char &sound: croakSequence) { // for each sound i.e. character. frequency[sound]++; // Note the sound. if (!isStateValid()) { // Make sure we are still in valid state. return -1; } if (sound == 'c') { // New "croaking" always begins at 'c'. numCroakingFrogs++; // Addional frog for the new "croaking". } else if (sound == 'k') { // A "croaking" ends at 'k'. numCroakingFrogs--; // Some frog has stopped croaking now. } answer = max(answer, numCroakingFrogs); // Maximum number of frogs that are // croakingsimultaneously over a period. } return numCroakingFrogs == 0 ? answer : -1; // Make sure all frogs have completed the // croaking. } };
view raw Leetcode_1419.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!