Filling a string with wildcards with minimum cost

Question

You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string.

You are allowed to write data to the string in blocks of fixed size: character-by-character, you can write contiguous blocks of identical characters of length 2, 3 ... N: X, XX, XXX, etc. For example:

Block: XX, apply to the 2 position in X***Y*Z => X*XXY*Z

It is allowed to overwrite same characters:

Block: XX, apply to the 0 position in X***Y*Z => XX**Y*Z

When you choose a size of block you would like to use, let's say S, "preparation" costs occurs: S*L, where L - some input constant. Let's say, you picked the size 2 (cost is 2*L), then you are allowed to write XX, YY, and ZZ to the given string. When you write a block of data to the given string, writing cost occurs - some input constant C that is independent of the block size. When you choose some block length, e.g. 2, you have to fill all blanks using block_size = 2, you are not allowed to decrease or increase it in the middle of writing. For example, if you write the first piece of data to the given string as XX, later you are allowed to use YY and ZZ only. The same with other sizes.

Your task is to identify the minimum possible cost to fill all blanks considering costs of writing data and preparing a block.

Let's consider the example above in details. We are given a string X***Y*Z, L = 20, C = 10. For each option, there are a plenty of variants how to fill blanks.

1) We can fill all blanks with a block of size 1 using any characters from {X, Y, Z}. Thus, total cost is 1*20 (prepare a block of size 1) + 4*10 (fill 4 wildcards) = 60. Possible results, there are plenty of them:

XYXZYXZ, XXXYYZZ...

2) We can use block size = 2. For example, overwrite X* with XX, ** with XX, Y* with YY, the total cost is 2*20 (prepare the block of size 2) + 3*10 (perform 3 writing operations to fill all blanks), the total cost is 70. Example:

Solution 1

Init: X***Y*Z

step1: write XX at 0 => XX**Y*Z

step2: write XX at 1 => XXX*Y*Z

step3: write YY at 3 => XXXYY*Z

step4: write ZZ at 4 => XXXXYYZ

My current approach is, basically, straightforward brute-force - start with block_size = 1, iterate it up to N, each time try to fill all the wildcards. If current block overwrites existing data, try changing symbol type accordingly (If a block consists of X, try using Y). If it's not possible, try another symbol type/block size.

Is there any better way?

Answer 1

I think I've found a solution (thanks, Yuval Filmus and D.W.!). It consists of 2 major steps:

1) Generate a valid string at minimal steps. You start traversing a string from left to right, moving by 1 character each time. I do this recursively. At each recursion level, you iterate a substring in a range [current_pos, block_size] and continue recursion from each character. By doing this you are exploring possibilities to print, let's say, 3 characters and to continue from any of them without any costs. During recursion, you explore all input characters: X, Y, Z, so each time you generate 3 branches. When you hit an end of a string, corresponding recursion depth equals to a number of used blocks.

2) Searching for an optimal block_size. Using binary search over a block's length to find the optimal block size could be tempting, but it does not work in general. The reason is that depending on costs of block's preparation/usage, cost function could be non-monotonic. Thus, it looks like you have to use linear search.