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.

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 :

http://discuss.codechef.com/questions/4698/use-of-modulo-1000007-in-competitions

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 .

@jaipal_543 please explain the question , like string made up of ? [a-z] [0-9] or any specific info?

thanq…made me feel very easy