I have written a solution for Cyclic shift question on Hackerearth.

You can find this question on Hackerearth -> Codemonk -> Arrays & String -> Cyclic shift.

This solution gives TLE for large testcases. How do i optimize this code.

It seems like Java does not handle strings efficiently. Same code in Python gets accepted.

import java.io.*;
import java.util.*;
class TestClass
{


    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int N; int K;
            N = sc.nextInt();
            K = sc.nextInt();
            String input = sc.next();
            String B = "";
            String inter = input;
            int d = 0;
            int period = -1;
            for(int i = 0; i < N;i  ){
                

                if (B.compareTo(inter) < 0){
                    B = inter;
                    d = i;
                    
                }else if (B.compareTo(inter) == 0){
                    period = i - d;
                    break;
                }
                inter = inter.substring(1, inter.length())   inter.substring(0, 1);
            }
            if(period == -1){
                System.out.println(d   (K - 1L ) * N);
            }else{
                System.out.println(d   ((K - 1L) * period));
            }
        }


    }
}

I tried fast IO, it did not help.

Please give me the Optimized Solution.

As suggested by maraca. Following solution does gets accepted.

import java.io.*;
import java.util.*;
class TestClass
{

    static int compare(LinkedList<Character> A, LinkedList<Character> B){
        Iterator<Character> i = A.iterator();
        Iterator<Character> j = B.iterator();
        if(A.size() == 0){ return -1;}
        while (i.hasNext()) { // we know they have same length
            char c = i.next();
            char d = j.next();
            if (c < d)
                return -1;
            else if (c > d)
                return 1;
        }
        return 0;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int N; int K;
            N = sc.nextInt();
            K = sc.nextInt();
            String input = sc.next();
            LinkedList<Character> B = new LinkedList<>();
            
            int d = 0;
            int period = -1;
            LinkedList<Character> inter = new LinkedList<>();
            for(char c: input.toCharArray()){inter.add(c);}

            for(int i = 0; i < N;i  ){
                if (compare(B, inter) < 0){
                    B = new LinkedList<>(inter);
                    d = i;
                    
                }else if (compare(B, inter) == 0){
                    period = i - d;
                    break;
                }
                inter.add(inter.removeFirst());
            }
            if(period == -1){
                System.out.println(d   (K - 1L ) * N);
            }else{
                System.out.println(d   ((K - 1L) * period));
            }
        }


    }
}

CodePudding user response：

Strings are immutable in Java. You could try to use LinkedList:

LinkdedList<Character> inter = new LinkedList<>(Arrays.stream(inter)
    .boxed()
    .collect(Collectors.toList()));

Alternatively:

LinkdedList<Character> inter = new LinkedList<>();
for (char c : input.toCharArray())
    inter.add(c);

Then the shift becomes:

inter.add(inter.removeFirst());

And the comparison can be done as follows:

private int compare(List<Character> a, List<Character> b) {
    Iterator<Character> i = a.iterator();
    Iterator<Character> j = b.iterator();
    while (i.hasNext()) { // we know they have same length
        char c = i.next();
        char d = j.next();
        if (c < d)
            return -1;
        else if (c > d)
            return 1;
    }
    return 0;
}