Solution

Approach #1 Brute Force [Time Limit Exceeded]

In the brute force approach, we actually form every possible string comprising of the letters "A", "P", "L" and check if the string is rewardable by checking it against the given criterias. In order to form every possible string, we make use of a recursive gen(string, n) function. At every call of this function, we append the letters "A", "P" and "L" to the input string, reduce the required length by 1 and call the same function again for all the three newly generated strings.

!?!../Documents/552_Student_Attendance_Record_II.json:1000,563!?!

Complexity Analysis

• Time complexity : $$O(3^n)$$ . Exploring $$3^n$$ combinations.
• Space complexity : $$O(n^n)$$ . Recursion tree can grow upto depth $$n$$ and each node contains string of length $$O(n)$$ .

Approach #2 Using Recursive formulae [Time Limit Exceeded]

Algorithm

The given problem can be solved easily if we can develop a recurring relation for it.

Firstly, assume the problem to be considering only the characters $$L$$ and $$P$$ in the strings. i.e. The strings can contain only $$L$$ and $$P$$ . The effect of $$A$$ will be taken into account later on.

In order to develop the relation, let's assume that $$f[n]$$ represents the number of possible rewardable strings(with $$L$$ and $$P$$ as the only characters) of length $$n$$ . Then, we can easily determine the value of $$f[n]$$ if we know the values of the counts for smaller values of $$n$$ . To see how it works, let's examine the figure below:

The above figure depicts the division of the rewardable string of length $$n$$ into two strings of length $$n-1$$ and ending with $$L$$ or $$P$$ . The string ending with $$P$$ of length $$n$$ is always rewardable provided the string of length $$n-1$$ is rewardable. Thus, this string accounts for a factor of $$f[n-1]$$ to $$f[n]$$ .

For the first string ending with $$L$$ , the rewardability is dependent on the further strings of length $$n-3$$ . Thus, we consider all the rewardable strings of length $$n-3$$ now. Out of the four combinations possible at the end, the fourth combination, ending with a $$LL$$ at the end leads to an unawardable string. But, since we've considered only rewardable strings of length $$n-3$$ , for the last string to be rewardable at length $$n-3$$ and unawardable at length $$n-1$$ , it must be preceded by a $$P$$ before the $$LL$$ .

Thus, accounting for the first string again, all the rewardable strings of length $$n-1$$ , except the strings of length $$n-4$$ followed by $$PLL$$ , can contribute to a rewardable string of length $$n$$ . Thus, this string accounts for a factor of $$f[n-1] - f[n-4]$$ to $$f[n]$$ .

Thus, the recurring relation becomes:

$$f[n] = 2f[n-1] - f[n-4]$$

We store all the $$f[i]$$ values in an array. In order to compute $$f[i]$$ , we make use of a recursive function func(n) which makes use of the above recurrence relation.

Now, we need to put the factor of character $$A$$ being present in the given string. We know, atmost one $$A$$ is allowed to be presnet in a rewardable string. Now, consider the two cases.

1. No $$A$$ is present: In this case, the number of rewardable strings is the same as $$f[n]$$ .

2. A single $$A$$ is present: Now, the single $$A$$ can be present at any of the $$n$$ positions. If the $$A$$ is present at the $$i^{th}$$ position in the given string, in the form: "<(i-1) characters>, A, <(n-i) characters>", the total number of rewardable strings is given by: $$f[i-1] * f[n-i]$$ . Thus, the total number of such substrings is given by: $$\sum_{i=1}^{n} (f[i-1] * f[n-i])$$ .

Complexity Analysis

• Time complexity : $$O(2^n)$$ . method $$func$$ will take $$2^n$$ time.

• Space complexity : $$O(n)$$ . $$f$$ array is used of size $$n$$ .

Approach #3 Using Dynamic Programming [Accepted]

Algorithm

In the last approach, we calculated the values of $$f[i]$$ everytime using the recursive function, which goes till its root depth everytime. But, we can reduce a large number of redundant calculations, if we use the results obtained for previous $$f[j]$$ values directly to obtain $$f[i]$$ as $$f[i] = 2f[i-1] + f[i-4]$$ .

Complexity Analysis

• Time complexity : $$O(n)$$ . One loop to fill $$f$$ array and one to calculate $$sum$$

• Space complexity : $$O(n)$$ . $$f$$ array of size $$n$$ is used.

Approach #4 Dynamic Programming with Constant Space [Accepted]

Algorithm

We can observe that the number and position of $$P$$ 's in the given string is irrelevant. Keeping into account this fact, we can obtain a state diagram that represents the transitions between the possible states as shown in the figure below:

This state diagram contains the states based only upon whether an $$A$$ is present in the string or not, and on the number of $$L$$ 's that occur at the trailing edge of the string formed till now. The state transition occurs whenver we try to append a new character to the end of the current string.

Based on the above state diagram, we keep a track of the number of unique transitions from which a rewardable state can be achieved. We start off with a string of length 0 and keep on adding a new character to the end of the string till we achieve a length of $$n$$ . At the end, we sum up the number of transitions possible to reach each rewardable state to obtain the required result.

We can use variables corresponding to the states. $$axly$$ represents the number of strings of length $$i$$ containing $$x$$ $$a's$$ and ending with $$y$$ $$l's$$ .

Below code is inspired by @stefanpochmann.

Complexity Analysis

• Time complexity : $$O(n)$$ . Single loop to update the states.

• Space complexity : $$O(1)$$ . Constant Extra Space is used.

Approach #5 Using less variables [Accepted]

Algorithm

In the last approach discussed, we've made use of six extra temporary variables just to keep a track of the change in the current state. The same result can be obtained by using a lesser number of temporary variables too.

Complexity Analysis

• Time complexity : $$O(n)$$ . Single loop to update the states.

• Space complexity : $$O(1)$$ . Constant Extra Space is used.

Analysis written by: @vinod23