1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ So the counts are both "allowed" and "required", right? Therefore we know exactly the number of X and Y in the string s? $\endgroup$
    – gnasher729
    May 26, 2022 at 15:04
  • $\begingroup$ @gnasher729 yes! You have to use all of the given building blocks. $\endgroup$
    – Looft
    May 26, 2022 at 15:24
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    May 26, 2022 at 16:56
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W.
    May 27, 2022 at 6:06
  • $\begingroup$ @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. $\endgroup$
    – Looft
    May 27, 2022 at 11:41

1 Answer 1

1
$\begingroup$

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.

In your example:

eps = empty 
X = X
XX = X, X (no XX available)
XXY = X, XY (preferred to X, X, Y)
XXYX = X, XY, X (no XY available)
XXYXY = X, XY, X, Y.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.