Filling a string with wildcards with minimum cost
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.