Find the number of palindromic strings that can be made of length N, or less
It might be useful to see a link to the question you are trying to solve so we can get a better idea of the constraints. In a general sense though a palindromic string is one that can be read the same forwards and backwards so for example:
"aba" //this is a palindromic string
"abab" //this is not a palindromic string
If you are given a number N and asked to find the number of palindromic strings of length N or less you first need to know if you only need to worry about strings containing alphabetic characters if so are we dealing with [a-z], [A-Z] or both? If we can properly constrain the problem solving it shouldn’t be so bad.
@jaipal_543 please explain the question , like string made up of ? [a-z] [0-9] or any specific info?
A link would be good. . .
@jaipal_543 : Let C be the number of allowed characters to use in the string .
If the string has length k , then you can choose k/2 ( rounded up ) characters arbitrarily and rest become automatically fixed .
So strings of length k which are palindromes = C^(roundUP(k/2)) .
So number of strings of length N or less which are palindromes is :
C^1 + C^1 + C^2 + C^2 … + C^(roundUP(N/2)) . [ total terms in sequence is N )
If N is even :
Answer = 2 * ( C^1 + C^2 … + C^(N/2) ) .
=> Answer = 2 * C * ( C^(N/2) - 1 ) / ( C - 1) .
In case C = 1 , Answer = N , since there is only one string of each particular length less than N
If N is odd :
Answer = Answer from above formula for N-1 + C^(roundUP(N/2)) .
Again in case C = 1 , Answer = N .
@jaipal_543 : The logic of the problem i have already explained .
Is it clear to you ?
In case of TPALIN , C = 26
You will need the concept of “MODULAR MULTIPLICATIVE INVERSE” to solve it .
To learn that you may refer to :
I have explained modulo calculations there .
Best of luck in solving the problem , and happy coding .
Please feel free to ask any query if something is unclear to you .
thanq…made me feel very easy