May 05, 2020

Description:

Given the string croakOfFrogs, which represents a combination of the string "croak" from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid "croak" means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid "croak" return -1.

 

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1 
Explanation: One frog yelling "croak" twice.

Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2 
Explanation: The minimum number of frogs is two. 
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".

Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.

Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1

 

Constraints:

  • 1 <= croakOfFrogs.length <= 10^5
  • All characters in the string are: 'c''r''o''a' or 'k'.

 

Solution:

# https://leetcode.com/problems/minimum-number-of-frogs-croaking/


class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        string = 'croak'
        croaks = []

        if (not croakOfFrogs):
            return len(croaks)

        # if first and last letters are not matching then return -1
        if (croakOfFrogs[0] != 'c' or croakOfFrogs[-1] != 'k'):
            return -1

        for c in croakOfFrogs:
            if (c not in string):
                return -1
            if (c == 'c'):
                # if there is a completed croak then replace it with len('c')
                # else add it as a new croak
                if (5 in croaks):
                    croaks[croaks.index(5)] = 1
                else:
                    croaks.append(1)
                continue

            # for every character other than 'c'
            # find it's index in 'croak'
            index = string.index(c)

            # If there is any substring which is followed by
            # current character is present in the croaks then
            # increase its length by 1
            # eg. if character is 'a' and its index in 'croak' is 3,
            # the length of substring which occurs before a is
            # also 3 (length of 'cro').
            if (index in croaks):
                croaks[croaks.index(index)] += 1
            else:
                return -1

        # finally len(croaks) gives the minimum number of frogs, 
        # check all croaks are complete, i.e all lengths in croaks 
        # list should be 5
        if (len(croaks) * 5 == sum(croaks)):
            return len(croaks)
        else:
            return -1

 

Explanation:

Like most of the string related problems, we can solve it in many different ways. Unless we comeup with an efficient algorithm with combination of suitable datastructures, we'll endup taking too much time resulting 'Time Limit Exceeded!like the above solution. This kind of problems indeed teach us the importance of the data structures in problem solving! Sometimes, the problem statement itself mis-guides us. In the description given above, it says we've to find the manimum number of frogs croaking given a string 'croakOfFrogs'. The same problem can be thought as 'the maximum number of concurrent croaks' that are present in the string.

The approach that I've followed, is to keep track of the occurances of the substrings of the word 'croak'. The progression of the 'croak' will be 'c' > 'cr' > 'cro' > 'croa' > 'croak'. When it encounters with letter 'c', it just simply checks for any complete 'croak' happend just earlier to it. If yes it removes the entry from croaks['croak'], otherwise it increases the count by 1. In both the above solution which results in 'Time limit Exceeded!' error and below one which passed all the test cases, uses the same algorithm but different data structures to keep track of the intermediate data.

 

Efficient Solution:

# https://leetcode.com/problems/minimum-number-of-frogs-croaking/


class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        string = 'croak'

        croaks = dict()
        frogs = 0

        # Base condition 1
        if (len(croakOfFrogs) % 5 != 0):
            return -1

        # Base condition 2
        if (croakOfFrogs[0] != 'c' and croakOfFrogs[-1] != 'k'):
            return -1

        # initiate a map to track the number of
        # 'c' >> 'cr' >> 'cro' >> 'croa' >> 'croak' had appeared
        for i in range(5):
            croaks[string[:i + 1]] = list()

        for c in croakOfFrogs:
            if (c == 'c'):
                # When we encounter a 'c' check whether
                # there is any complete croak happened earlier to it.
                # if not increase the number of frogs by 1
                # The reason is when a frog started croaking, i.e when there is a 'c' then
                #   i) There is no croak prior to it (OR)
                #   ii) A different frog/frogs is/are croaking and is/are not completed yet
                if (croaks['croak']):
                    croaks['croak'].pop()
                else:
                    frogs += 1
                croaks[c].append(1)

            elif (c == 'r'):
                if (croaks['c']):
                    croaks['c'].pop()
                    croaks['cr'].append(1)
                else:
                    return -1

            elif (c == 'o'):
                if (croaks['cr']):
                    croaks['cr'].pop()
                    croaks['cro'].append(1)
                else:
                    return -1
            elif (c == 'a'):
                if (croaks['cro']):
                    croaks['cro'].pop()
                    croaks['croa'].append(1)
                else:
                    return -1
            elif (c == 'k'):
                if (croaks['croa']):
                    croaks['croa'].pop()
                    croaks['croak'].append(1)
                else:
                    return -1
            else:
                return -1

        del croaks['croak']

        # If there is any incomplete croak then return -1
        if (any(croaks.values())):
            return -1

        return frogs

 

Evaluation: