given a string, characters can be shuffled to make a paliandrome.
What is the minimum possible number of insertions to original string needed so that it will be a palindrome (after shuffling, if required).
Input
T -> number of test cases
T number of Strings in different lines
import java.util.Arrays;
import java.io.InputStreamReader;
import java.io.BufferedReader;
public class Xsquare{
public static void main (String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int limit = Integer.parseInt(br.readLine());
int [] alphabets = new int[26];
while(limit-- >0){
String input = br.readLine();
Arrays.fill(alphabets,0);
char [] inpChar = input.toCharArray();
int sum = 0;
for (int i=0;i<input.length();i++){
int pos = (int)inpChar[i] - (int)'a';
alphabets[pos]+=1;
}
for(int i=0;i<26;i++){
if(alphabets[i]%2==0)
sum+=0;
else
sum+=1;
}
if(sum<=0)
sum=0;
else
sum-=1;
System.out.println(sum);
}
}
}
This is the code I submitted online. But it was not accepted as solution. What is the correct approach to this question?
1. You can make use of a Hashmap for each string. Each line is a string. Use a hashmap to count all the characters. If the length is odd, 1 character can appear once, rest all have to appear or the count has to be even for other characters. The characters that fall short of this condition are the number of characters required to make the string a palindrome. The you can just go over the hashmap, use two pointers front and rear to place the elements. Time complexity O(n) for the lines, O(T) for each string, So O(Tn) for the file containing all the strings.
- WilOzil November 26, 20152. Sort the string and count the characters. Follow similar approach as in case 1.
Time complexity O(n) for lines, O(TlogT) for sorting. O(nTlogT) in total.