# Filling a string with wildcards with minimum cost

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?

• @D.W. The problem came from outdated (~2012) local contest. See my update to the post itself. – CaptainTrunky Feb 27 '18 at 0:12
• You can improve your algorithm by using binary search. – Yuval Filmus Feb 27 '18 at 14:37