Red Rover

This problem asks us to compress a string by encoding a substring as a metacharacter any time it occurs.

There are only 100 characters. Can we brute force it? There are only 99^2=9801 possible substrings. So how would we evaluate a substring?

Can we just walk the string and substitute the substring every time it occurs? What if instances of the substring overlap? Does greedy work? or do we need to DP?

Lets consider our typical greedy proof by contradiction.

Suppose it was not optimal to choose the first instance of a substring. That means the next instance of the substring must overlap this one (otherwise we could choose this one with no consequence!). In such a case, the next place after that in which we could find the substring is strictly greater than if we had chosen the first substring. This gets us no benefit, meaning it is at least as optimal to select the first instance of the substring.

So do greedy replacement of the substring to figure out how many characters it saves and output the best.

Note: do NOT actually replace the strings as you are doing this. Simply remember where the next place you can match is.

Note: doing a naive string match is PROBABLY too slow. Matching at a given position is O(t) where t is token length, and you have to match O(s-t) characters. This is O(s^2), which when multiplied by total number of substrings is too high (10k * 100^2). It might work if the constant is low enough. Coders will instead have to implement KNP search or use built in functions. Java has string.indexOf() which takes an optional index parameter which is index at which the search should start. This should work. [[Category:Greedy