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:
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 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.