You may assume that optimal program will not have to modify more than four memory cells.
Does this mean that an optimal solution only uses 4 out of the 30000 given cells? If not, can someone clarify it?

The statement is ambiguous. The input string contains only letters ('a'-'z') and the array of 30000 memory cells is full of 0. It seems that all the cells should be modified. Please clarify this.