# Generating longest palindrome by switching only k digits

//This program generates a maximum possible palindrome from of a string num 's', of length 'n', by switching only 'k' digits.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int k=scan.nextInt();
String s=scan.nextLine();
s=scan.nextLine();

int ar[]=new int[n];
int i=0;
for(i=0;i<n;i++) //Forming an array to store the numbers.
ar[i]=s.charAt(i)-48;

int k2=count(ar,n); //counts the numbers to be switched.

if(k2>k) //if numbers to be switched are more than 'k', then palindrome will not form.
System.out.print(-1);

else {
int x=0,y=n-1;

while(k>k2 && (x<y)) { //if the given limit 'k' is more than normal exchanges, then swap adjacent numbers by 9, to get maximum palindrome
if(ar[x]!=ar[y]) {
ar[x]=9;
ar[y]=9;
x++;
y--;
k-=2; //since two changes have been made.
}
}

while(k>0 && (x<y)) { //now just changing one number with the adjacent, by the greater of the two.
if(ar[x]!=ar[y]) {
ar[x]=Math.max(ar[x], ar[y]);
ar[y]=ar[x];
k--;
}
x++;
y--;
}

if(k>0 && n%2!=0) //Now if all possible switches are done, and still allowed 'k' is left, then change the middle digit by 9, to get maximum number.
ar[x]=9;

for(i=0;i<ar.length;i++) //printing the number.
System.out.print(ar[i]);
}
scan.close();
}

static int count(int x[],int n) { //calculates the count of necessary switches.
int t1=0,t2=n-1,c=0;
while(t1<t2) {
if(x[t1]!=x[t2])
c++;
t1++;
t2--;
}
return c;
}
}


Whenever an Online judge checks it, 20/32 I get Terminated due to Timeout. I have tried every possible thing I know. I guess its time to learn something new...

• Hi. Welcome to Code Review! Does this work in local testing? What inputs have you tried? What online judge are you using? Is there a problem statement that gives things like a limitation of how long the input can be? – mdfst13 May 22 '16 at 11:37
• @mdfst13 This code runs perfectly in my PC and it even passed for most of the inputs given to it, 11/32 to be more precise. But for the remaining it gave Time Limit exceeded. This problem was in HackerRank so its there online judge. And this are the limitations of the inputs: 0 < =n < =10^5 0 < =k <= 10^5 Thanks for replying... – Shadow_Sphynx May 22 '16 at 14:33