A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. Givena palindrome write a program to print the sorted list of all palindromes that can be constructedfrom the alphabets of the given palindrome. All palindromes should start in a newline.Input Format :The first line, an integet T, indicating the number of test cases T lines each containing one string(palindrome)Output Format:Print sorted list of all palindromes constructed from the given palindrome of the ith test case. Ifthe entered string is not a palindrome, then it should print as Not a palindrome.Sample Test Case:TSample Input:1NITINSample Output:INTNI
Answers
Answer:
// C++ program to count special Palindromic substring
#include <bits/stdc++.h>
using namespace std;
// Function to count special Palindromic susbstring
int CountSpecialPalindrome(string str)
{
int n = str.length();
// store count of special Palindromic substring
int result = 0;
// it will store the count of continues same char
int sameChar[n] = { 0 };
int i = 0;
// traverse string character from left to right
while (i < n) {
// store same character count
int sameCharCount = 1;
int j = i + 1;
// count smiler character
while (str[i] == str[j] && j < n)
sameCharCount++, j++;
// Case : 1
// so total number of substring that we can
// generate are : K *( K + 1 ) / 2
// here K is sameCharCount
result += (sameCharCount * (sameCharCount + 1) / 2);
// store current same char count in sameChar[]
// array
sameChar[i] = sameCharCount;
// increment i
i = j;
}
// Case 2: Count all odd length Special Palindromic
// substring
for (int j = 1; j < n; j++)
{
// if current character is equal to previous
// one then we assign Previous same character
// count to current one
if (str[j] == str[j - 1])
sameChar[j] = sameChar[j - 1];
// case 2: odd length
if (j > 0 && j < (n - 1) &&
(str[j - 1] == str[j + 1] &&
str[j] != str[j - 1]))
result += min(sameChar[j - 1],
sameChar[j + 1]);
}
// subtract all single length substring
return result - n;
}
// driver program to test above fun
int main()
{
string str = "abccba";
cout << CountSpecialPalindrome(str) << endl;
return 0;
}
Language used : Python Programming
Program :
from itertools import permutations
nt=int(input())
flag=0
while(flag!=nt):
st=""
st=str(input())
if st==st[::-1]:
update=[st]
st=list(st)
perm=permutations(st)
for i in perm:
check=''.join(i)
if check==check[::-1]:
if check not in update:
update.append(check)
print(check)
if len(update)==1:
print("Doesn't form any other palindrome")
else:
print("Not a palindrome")
flag=flag+1
Inputs and outputs :
Test case 1 : (opting for 1 test case)
Input :
1
NITIN
Output :
INTNI
Test case 2: (Opting for 4 test cases)
Input : (1)
4
NITIN
Output :
INTNI
Input : (2)
RACECAR
Output:
RCAEACR
ARCECRA
ACRERCA
CRAEARC
CARERAC
Input : (3)
BOB
Output :
Doesn't form any other palindrome
Input : (4)
HAPPY
Output :
Not a palindrome
Explanation :
- First take no.of test cases n as an input and write a while loop to run it for n times.
- Entering the loop ask user to enter a string.
- Check whether the string is palindrome or not. If yes, using permutations, take all the possibilities into a list variable. Else, print a statement stating that it isn't a palindrome.
- If it is a palindrome, form a list immediately and insert that palindrome into the string.
- Write a for loop that checks each probability by joining the substrings of a sub list that forms a word, whether it is palindrome or not.
- If the probable string is in list, ignore to print. Else, append the new string to the list and then print it.
- After all the probabilities of a string, are checked and the new palindromes are printed, initialize all the in loop things back to empty.
- If you find no other palindrome is happened by checking len(list)==1 (that 1 is of the original string), print a statement stating that.
- Update the flag variable by incrementing it to 1, and let the loop keep on running till that flag value equals to the no.of test cases entered. That's it!
Learn more :
- Advantages of Programming in python
brainly.in/question/11007952
- Indentation is must in python. Know more about it at :
brainly.in/question/17731168
