the logic behind this was (n-2)3^(n-3) has lots of repetitons like (abc)***(abc) when abc is at start and at end and the strings repated total to 3^4 . similarly as abc moves ahead and number of sets of (abc) increase
3 Answers
You can use dynamic programming to compute the number of forbidden strings.
The algorithms follow from the observation below:
"Legal string of size n is the legal string of size n - 1 extended with one letter, so that the last three letters of the resulting string are not all distinct."
So if we had all the legal strings of size n-1 we could try extending them to obtain the legal strings of size n.
To check whether the extended string is legal we just need to know the last two letters of the previous string (of size n-1).
In the algorithm we will compute two arrays, where
different[i] # number of legal strings of length i in which last two letters are different
same[i] # number of legal strings of length i in which last two letters are the same
It can be easily proved that:
different[i+1] = different[i] + 2*same[i]
same[i+1] = different[i] + same[i]
It is the consequence of the following facts:
Any 'same' string of size i+1 can be obtained either from 'same' string of size i (think BB -> BBB) or from 'different' string (think AB -> ABB) and these are the only options.
Any 'different' string of size i+1 can be obtained either from 'different' string of size i (think AB-> ABA ) or from the 'same' string in two ways (AA -> AAB or AA -> AAC)
Having observed all this it is easy to write an algorithm that computes the result in O(n) time.
2 Comments
Dunes
There is a problem in your reasoning. Given
total[i] = same[i] + different[i], and total[i+i] = total[i] * 3 (eg. add a, b, or c to each string). Then by substituting your equations with my equations for total then your total[i+1] would be different[i]*2 + same[i]*3, whereas it should be different[i]*3 + same[i]*3
tkleczek
@Dunes: But in 'different' and 'same' arrays we count the number of legal strings. For legal strings it is not true that total[i+1] = 3*total[i].
I suggest you use recursion, and look at two numbers:
- F(n), the number of legal strings of length n whose last two symbols are the same.
- G(n), the number of legal strings of length n whose last two symbols are different.
Is that enough to go on?
5 Comments
Dinesh Kukreja
how would the similarity or disimilarity of last two symbols help..and for that i need to generate all the strings..
Dinesh Kukreja
is it possible to remove the repetition using permutations
Beta
@DineshKukreja, do you understand recursion (in the mathematical sense)? The idea here is that there is a simple method to go from the n case to the n+1 case. I've divided the problem into F and G for reasons that should become clear once you get into it. Given F(n) and G(n), can you calculate F(n+1) and G(n+1)?
Dinesh Kukreja
can u explain me your logic . how will the last two letters help me determine if string conatin abc or not .
Beta
@DineshKukreja, You're approaching it from the wrong direction. Imagine you have a legal string, and you want to add one letter to the end of it and keep it legal. Is that enough or should I spell it out?
get the ASCII values of the last three letters and add the square values of these letters. If it gives a certain result, then it is forbidden. For A, B and C, it would be fine.
To do this:
1) find out how to get characters from your string.
2) find out how to get ASCII value of a character.
3) Multiply these ASCII values with themselves.
4) Do that for the three letters each time and add their values.
1 Comment
Dinesh Kukreja
can u pls guide me how yd it help
homework, no one will be mad at you :) And you can share your experiences so far in solving the problem. And I think the problem needs some clarification..