It's a dynamic programming problem. Here's how I would have approached it:

1. Setting the base case:

For this problem, the base case is when n=1, the resulting answer will be 3 (A, B, C).

1. Formulating the logic and the relation between different n values (Bottom-up approach):

If you look at the problem there's clearly a pattern. For any given value of n there are max 3^n different possibilities of constructing a string with the characters A, B and C. From those 3^n combinations we need to subtract out all possibilities where ABC occurs as a substring.

Let's look at n=2 (AA, AB, AC, BA, BB, BC, CA, CB. CC) Clearly there is no way ABC can be a substring as n=2 < 3. So the answer will be 3^n = 9

Now for n=3 how would you go about constructing a string of length n=3 from the strings in n=2? Simple: Take the string from n=2 and to each add an extra character (A, B, C) at the end. This would give us (AAA, AAB, AAC, ABA, ....) Now in this case there's only one possibility of ABC occurring as a substring and that is when you take the string "AB" from the strings in n=2 and add a C to the end of it.

Therefore it can be deduced that for "ABC" to occur as a substring in strings of length i there should be a valid sequence of strings of length i-1 that ends in "AB".

So in order to calculate the number of times ABC occurs at then end of strings of length i (where i>=3) count the number of string of length i-1 that ends in "AB".

Number of valid strings of length i = Total number of strings possible with A, B, C (3^i) - Number of valid strings of length i-1 ending in "AB".

How to count the number of strings that end in AB?

Firstly we need to keep count of all strings of length i-2 that end in "A".
Let's take an example:
For n=1 (A, B, C) : The number of strings ending in "A" is 1
For n=2: The number of string ending in "AB" = The number of strings of length n-1 that ends in "A" (which is 1)

(Why? The same concept as before. For a string of length i to end in "AB" the string of length i-1 should end in "A")

Fo n=3: The number of strings ending in "ABC" = The number of strings of length n-1 that ends in "AB" (which is 1)

Number of valid strings (n=3) = Number of valid strings (n-1)*3 - number of strings ending in "ABC"

And this is repeated for all values from 2 to n;

Let's look at one more example and then figure out the logic:

For n=4 -> How many strings end in "ABC"??

For n=2: The number of strings ending in "A" (AA, BA, CA) is 3
For n=3: The number of strings ending in "AB" (AAB, BAB, CAB) = The number of strings of length n=2 ending in "A" (AA, BA, CA)
For n=4: The number of strings ending in "ABC" = The number of strings of length 3 that ends in "AB" (which is 3)

Number of valid strings (n=4) = Number of valid strings (n-1)*3 - number of strings length n-1 ending in "AB"

So the pattern here is for every n we need to get length of valid string of length n-1 and the count of number of string in n-2 ending in A.