String Modification : Challenge | Combinatorics | Mathematics | HackerRank
Roy was given a string s containing only uppercase English letters. He can do any number of modifications on s. The allowed modifications are:
He can add underscore ('_') character in anywhere inside the string.
He can delete any existing character of the string.
He can swap any two characters of the string.
Every character in the resulting string has a value equal to its ASCII value.
After doing the modifications the string needs to have the following properties:
The length of the string should be equal to n.
There should be at least k characters of higher value between two equal letters (Note that, underscore is not a letter).
Calculate how many different strings Roy can achieve modulo1000003 (10
6+3) .
Note: In the increasing order of ASCII value, we can arrange the alphabet in the following way,
⋯ <
After the modifications, any number of letters can be deleted froms , any number of underscore characters will be added to s , any of the possible arrangements of existing letters can exist and the length of the string will be equal to n . So, if we calculate the result for all possible counts of each letter, we will be able to get the answer.
The dynamic programming solution involves two states(i,j) , i is the index of current letter and j is the number of letters taken having value smaller than i . Iterate over all possible number of occurrences of i , t (t≤min(n−j, number of ith characters in s)) . Count the number of ways to place t characters in the remaining field keeping a gap of at least k between them. These k gaps will either be filled with letters with bigger value or underscore characters and thus maintain the conditions stated in the problem.
The number of ways in which we can putr characters in a field of n by keeping a gap of at least k is (n−(k×(r−1))r) . As the result needs to be calculated modulo some prime, I used lucas theorem to calculate that.
http://www.cnblogs.com/tonix/p/4513975.html*DP Part: there is dependency between letters: you should pick higher chars then lower chars, and DP choice occurs during this process.
Read full article from String Modification : Challenge | Combinatorics | Mathematics | HackerRank
Roy was given a string s containing only uppercase English letters. He can do any number of modifications on s. The allowed modifications are:
He can add underscore ('_') character in anywhere inside the string.
He can delete any existing character of the string.
He can swap any two characters of the string.
Every character in the resulting string has a value equal to its ASCII value.
After doing the modifications the string needs to have the following properties:
The length of the string should be equal to n.
There should be at least k characters of higher value between two equal letters (Note that, underscore is not a letter).
Calculate how many different strings Roy can achieve modulo
Note: In the increasing order of ASCII value, we can arrange the alphabet in the following way,
A<B<C<D<X<Y<Z<_After the modifications, any number of letters can be deleted from
The dynamic programming solution involves two states
The number of ways in which we can put
http://www.cnblogs.com/tonix/p/4513975.html*DP Part: there is dependency between letters: you should pick higher chars then lower chars, and DP choice occurs during this process.
*Maths Part: C(m + n, n) is used, but the numbers are huge, so regular combination formula is not working here. Lucas Theorem is necessary here (http://en.wikipedia.org/wiki/Lucas%27_theorem), which I will try to understand later..
Read full article from String Modification : Challenge | Combinatorics | Mathematics | HackerRank
