PROBLEM LINK:
Author: Man Mohan Mishra
Editorialist: Swapnil Saxena
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming
EXPLANATION:
The question is to find the count of string over alphabet {‘A’, ‘B’, ‘C’} which donot contain “ABC” as a substring. One can use a dp to approach the solution. Just keeps a track of last two characters as you move foreward. Consider a function f(i, prev_prev_char, prev_char) where f(i, prev_prev_char, prev_char) is the count of strings upto i such that second last used character is ‘prev_prev_char’ and last used character is ‘prev_char’. Clearly if prev_prev_char == ’A’ and prev_char == ’B’ one cannot use C as his currect character. Otherwise all possibilities (‘A’ or ‘B’ or ‘C’) are allowed. Time Complexity for the approach is (n33) * 3 = 27*n = O(n)
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.