Problem : Palindrome sorting
A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. Given a palindrome write a program to print the sorted list of all palindromes that can be constructed from the alphabets of the given palindrome. All palindromes should start in a newline.
Input Format:
One string (palindrome)
Output Format:
A sorted list of all palindromes constructed from the given string. Each line should contain one palindrome.
Example 1
Input
NITIN
Output
INTNI
NITIN
Explanation
There are only two palindromes that can be constructed from NITIN
Example 2
Input
ABCDCBA
Output
ABCDCBA
ACBDBCA
BACDCAB
BCADACB
CABDBAC
CBADABC
Explanation
Since there is only one D, it can only be the middle letter in the palindrome. The remaining lettere A, B, C can be arranged in 6 possible ways and each way gives rise to a palindrome.
1 Like
Just break this problem in two parts:
- find first smallest palindrome
- Find next string of left part of string(left side of mid char or say s[:len(s)/2]) and create palindrome then as leftPart + midChar + leftPart[::-1]
For first part, it would easy:
- just find all different characters that is used in string
- Find frequencies of each char in string, decrease frq by 1 for odd frq char(assuming there will be 0 or 1 char with odd frq).
- And just make a left string out of these strings using half of their frqs and use them in increasing order.
- now smallest palindrome would be leftString(find from above steps) + midChar(odd frq char) + leftString[::-1]
For second part you just have to find next lexicographical bigger string of left string that you found from above steps. and create palindrome out of it in same way.
You can take help from here to find next lexicographical bigger string. In C++ you can use next_permutation(s.begin(), s.end()) in algorithm where s is string for which you have to find next permutation.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class palindromeWithoutDuplicate {
public static void main(String[] args) {
int j,n,i=1,m=0;
ArrayList< String> p=new ArrayList<>();
Scanner scanner=new Scanner(System.in);
ArrayList<String> al = new ArrayList<String>();
Set <String> resultSet=new HashSet<String>();
String str=scanner.next();
StringBuilder sb1 = new StringBuilder(str);
sb1.reverse();
if(str.equals(sb1.toString())){
String pq = null;
printCombinations(str, 0, str.length(),resultSet);
Object[] finalArray=resultSet.toArray();
for(Object s:finalArray){
StringBuilder sb=new StringBuilder(s.toString());
sb.reverse();
if(s.toString().equals(sb.toString())){
al.add(s.toString());
s = null;
}
}
Collections.sort(al);
p.addAll(al);
}
for(String s: p){
System.out.println(s);
}
}
public static void printCombinations(String str,int k,int n,Set<String> resultSet){
for(int i=k;i<n;i++){
String temp=modifyString(str,i,k);
resultSet.add(temp);
printCombinations(temp,k+1,n,resultSet);
}
}
public static String modifyString(String str,int x,int y){
char arr[]=str.toCharArray();
char t= arr[x];
arr[x]=arr[y];
arr[y]=t;
String s= new String(arr);
return s;
}
}
#include <stdio.h>
#include <string.h>
char str[10];
int j;
char node[50][50];
void sort()
{
char temp[50];
for(int i=0; i<j; ++i)
for(int k=i+1; k<j; ++k)
{
if(strcmp(node[i],node[k])>0)
{
strcpy(temp, node[i]);
strcpy(node[i], node[k]);
strcpy(node[k], temp);
}
}
for(int i=0; i<j; ++i)
printf("%s\n",node[i]);
}
void swap(char *x, char *y,char *z,char *t)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
temp = *z;
*z = *t;
*t = temp;
}
void permute(char *a, int l, int r)
{
int n=strlen(str);
int i;
if (l==r)
{
strcpy(node[j],a);
j++;
}
else
{
for (i = l; i <= r; i++)
{
swap((a+l),(a+i),(a+(n-1-l)),(a+(n-1-i)));
permute(a, l+1, r);
swap((a+l),(a+i),(a+(n-1-l)),(a+(n-1-i)));
}
}
}
int main()
{
scanf("%s",str);
int n = strlen(str);
int temp=n/2;
permute(str, 0, temp-1);
sort();
return 0;
}
1 Like