Leetcode #1419: Minimum Number of Frogs Croaking

Link to the Problem

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.

Leetcode #1419: Minimum Number of Frogs Croaking - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms
Leetcode #1419: Minimum Number of Frogs Croaking – Diagram to assist visualization

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<char, int> 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!

Similar Problems

Leetcode #242: Valid Anagram
Leetcode #1446: Consecutive Characters



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s