Issue with Campaign problem to find distinct valid campaigns

I have encountered this problem as part of tech interview prep. However, I am not able to identify on how to solve the problem.


An email campaign is a sequence of email messages, where each email message belongs to one of two types, transactional or marketing.

M T T M M T T M M T Marketing messages are subject to a cooldown of length k. Within a given campaign, there must be at least k transactional emails between any two marketing emails.

For example, if k=2, the campaign

M T T M T T T M T is valid because between any two marketing emails there are at least two transactional emails. However, the campaign

M T M T T T T M T is invalid because there is only one transactional email separating the first two marketing emails. Note that, thus, there can never be two consecutive marketing emails or the pattern M T M.

Given the campaign length n and the cooldown length k, find the number of distinct valid campaigns. For example, there are 9 distinct campaigns of length 5 with k=2:

Sample solution:

T T T T T M T T T T T M T T T T T M T T T T T M T T T T T M M T T M T M T T T M T M T T M 

My Approach:

My initial thoughts were around generating all the valid permutations for each scenario and then counting it. However, I am not sure if that’s the way to go!

Would appreciate any insights.