I've been bashing my skull at this problem for some time now, and its really starting to frustrate me. The problem is:I have a set of characters, A, B, C, and D. I have to tell in how many ways a string can be built from those characters, when the length is n and each character must occur even times.For example, the answer for n = 2 is 4:AABBCCDDThe answer for n = 4 is 40. Some of those valid strings are:AAAAAABBCACADAADBCCBI'm stuck at coming up with a logic. I feel like there could be a DP solution for this. Brute-forcing my way through this is out of the question: the number of solutions rapidly grow into huge numbers.I've tried drawing all kinds of ideas on paper, to no avail. Almost all of those ideas I had to discard as their complexity was too big. The solution should be efficient for n = 10^4.One of my ideas was to never keep track of the actual strings, but only whether each character has appeared even or odd times. I couldn't come up with a way to apply this logic.Can anyone help me?
number of strings, when each character must occur even times
algorithms;strings;dynamic programming