# Determine if string can be constructed from given building blocks

Let's say building blocks are X, Y, XX, YY, XY and YX. Each building block has an associated count ($$c_X, c_Y, c_{XX}, \ldots$$, $$c_i$$ can be 0).

Given a string $$s$$ and building block counts, figure out if it can be constructed from the building blocks that are used exactly the amount of times allowed by counts.

Example: XXYXY, $$c_X=2, c_{XY}=1, c_{Y}=1$$ is possible, because X|X|Y| XY (there's more than 1 possible way to build the given string).

My approach was counting the appearances of building blocks in the string $$s$$. It's easy to figure out of there isn't enough X or Y to create the string, but a bit harder to figure out if there's too much XY and YX.

I expect that the algorithm is linear but I cannot figure it out.

• So the counts are both "allowed" and "required", right? Therefore we know exactly the number of X and Y in the string s? May 26, 2022 at 15:04
• @gnasher729 yes! You have to use all of the given building blocks. May 26, 2022 at 15:24
• To reduce the number of possibilities: If you have the choice between using a two-letter block or two single-letter blocks, you can always use the two-letter block - If you run out of two letter blocks later, you can use the two single letter blocks instead. May 26, 2022 at 16:56
• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
May 27, 2022 at 6:06
• @D.W. I managed to construct a DP algorithm that has complexity $O(N \prod c_i)$ which is too far away from linear time. Given that greedy approach of first exhausting multiletter blocks and then using up single letter blocks works quite well, I am in search of a linear time algorithm. May 27, 2022 at 11:41

For every prefix of the string, determine how it can be produced. We always prefer two letter blocks to two single letter blocks.

Let s = eps: Create s by using no blocks.

Let s = A where A is a single letter X or Y. s cannot be created if $$c_A = 0$$, otherwise it is created by using the single-letter block A.

Let s be a string of length n+2, ending in AB. It can be created in various ways. If there is a two letter block AB left then s is created by adding AB to every solution for the first n letters. If there is a single letter block B left then we add a single letter block B to any solution for the first n+1 letters that ended in a two-letter block, and to any solution for the first n+1 letters that ended in A unless there is a two letter block AB left. Then we remove all duplicates with the same number of each block lefts. That's it.

eps = empty

This will grow at most with $$2^n$$ where n is the number of letters, but is likely easier in practice, and possibly easier in the worst case as well.