### 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 (n*3*3) * 3 = 27*n = O(n)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.