2
$\begingroup$

A palindrome is a set of characters which equal the same thing forwards and backwards, for example; abccba

For a set of a given amount of characters (we can use 9 as an example) how would you calculate the amount of palindromes of characters mathematically?

This doesn't mean the words that can be formed but rather characters which are the same at start characters and end characters.

What formula can be used to calculate this for simple lengths like 9 with lowercase letters?

$\endgroup$
  • $\begingroup$ My apologies; may i ask what I did incorrectly to receive a downvote? I'd love to improve. $\endgroup$ – Oliver K Sep 15 '17 at 3:43
1
$\begingroup$

It depends (slightly) on whether you want an odd number of digits in your string, or an even number of digits in your string.

Let's say that the "alphabet" contains $N$ different "characters". (These could be the digits 1-9, or the letters A-Z, or any other set of distinguishable symbols.) You want to know how many palindromes of a given length there are.

If the string length is to be even: Say the string length is $2k$. You can choose each of the first $k$ characters to be anything you want; once you've chosen those, the rest of the string is forced on you by the required symmetry. So there are $k$ free choices, each drawn from a set of $N$ characters; that means there are $N^k$ possibilities.

If the string length is to be odd: Say the string length is $2k+1$. You can choose each of the first $k+1$ characters to be anything you want; once you've chosen those, the rest of the string is forced on you by the required symmetry. So there are $k+1$ free choices, each drawn from a set of $N$ characters; that means there are $N^{k+1}$ possibilities.

So, for example, if your alphabet consists of the 26 lowercase letters a-z, and you want a string with 9 characters, then $N=26$ and the string has length $2k+1$ with $k=4$; therefore the number of possible palindromes is $26^5=11,881,376$.

$\endgroup$
  • $\begingroup$ What a helpful explanation, thanks so much! $\endgroup$ – Oliver K Sep 15 '17 at 3:42
-1
$\begingroup$

include

include

include

using namespace std; int main() {
string s,s1,s2; cin>>s; s1 = s.substr(0,s.length()/2+1); int x = (s.length()%2 ==0 ) ? s.length()/2 : s.length()/2 + 1; s2 = s.substr(s.length()/2,x); string s3 = s2; for(int i=0;i

for(int i=0;i<s1.length() ; i++)
{
    if(s1[i]!=s3[i])
    {   
        s3 = s3.substr(0,i)+ s1[i] +s3.substr(i,s3.length()-i);

        if(s1[i+1]!= s3[i+1])
       { cout<<"NA";
        return 0;
       }
    }

}
s2=s3;
 for(int i=0;i<s3.length()+1;i++)
{
    s2[i]=s3[s3.length()-i-1];
}
cout<<s1<<s2.substr(1,s2.length());
return 0;

}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.