Leetcode 1419: Minimum Number of Frogs Croaking

In this Leetcode problem, we find the maximum number oof concurrent “croak” being spoken given an input string.

Problem statement

To solve this problem, we need to keep track of the words being spoken at each moment.

To do that, we introduce int[] current = new int[4] to keep track each word and at which character is the word being spoken. current[0] represent the number of words being spoken and for which the last letter spoken was c , same for current[1] and r.

For instance, in example 2: croakOfFrogs = "crcoakroak", here is the sequence of states after reading each character. We also will keep track of the sum of all the ints in the array currentC:

c -> [1, 0, 0, 0] currentC = 1
r -> [0, 1, 0, 0] currentC = 1
c -> [1, 1, 0, 0] currentC = 2
o -> [1, 0, 1, 0] currentC = 2
a -> [1, 0, 0, 1] currentC = 2
k -> [1, 0, 0, 0] currentC = 1
r -> [0, 1, 0, 0] currentC = 1
o -> [0, 0, 1, 0] currentC = 1
a -> [0, 0, 0, 1] currentC = 1
k -> [0, 0, 0, 0] currentC = 0

To know which index to update, for each character c we call "croak".indexOf(c), we could also use a Map but it was slightly easier to write that way.

The time complexity of this algorithm is O(n) with n the length of the string, since all operation take a constant time when we process each character.