11569 - Lovely Hint - UVA

backtracking

The problem wants you to count all the strings that you can construct under the restriction in the problem and print the length of the longest and the ways you can achieve that length.

Simply I start backtracking from all the characters and in the function you just backtrack with the characters that can be placed next to the current character under the restriction.
Each time I invoke the function for a character, I mark it, then I just pick it once.
Be careful! Don't invoke the function for 'L' in "HELLO" twice.

if( line[i] != line[i-1] && !mark[i] && 5 * (line[cur]-'A'+1) <= 4 * (line[i]-'A'+1) )
{
mark[i] = true;
solve( i, d+1 );
mark[i] = false;
}

I sort the input string, something like this is the main condition in the function.
'i' is the current character I'm checking, 'd' is the length of the string I've made till now.

length[d ++]
This array tracks how many strings up to 'd' characters I can construct.
At last I find the maximum length and print length[maximum_length].