2
\$\begingroup\$
//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...

\$\endgroup\$
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – mdfst13 May 22 '16 at 11:37
  • \$\begingroup\$ @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... \$\endgroup\$ – Shadow_Sphynx May 22 '16 at 14:33

Your Answer

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

Browse other questions tagged or ask your own question.