CDSW152 - Editorial

PROBLEM LINK:

Practice

Contest

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.

//