The similarity of two strings is defined as the length of their longest common subsequence. That, in turn, is defined as the longest string that can be obtained from both strings by dropping some characers. For example, the similarity of strings CATGT and GACTT is 3, as they have common subsequences of length 3, ATT and CTT, but no common subsequence of length 4.
You are given a string consisting of letters A, C, G, T (by far the most popular background for string problems these days :)). You need to find another string consisting of those four letters, and of the same length as the given string, that is least similar to the given string. Of course, there might be many such strings - for example, for CATGT discussed above there any many strings of the same length with similarity 1, like GAACC or TAAAC.
Can you solve it quickly?
This problem is not difficult, but I've enjoyed receiving "Accepted" from the judging system for this problem a lot. Most contests need easy problems, and it is so much better when those problems are not "easy because you just have to implement what's described in the problem statement", but "easy because you can just figure it out quickly".