如何优化Hackerearth CyclicShift问题的Java代码以解决超时（TLE）问题

I’ve run into exactly this kind of string manipulation-induced timeout issue in Java before, so I totally get your frustration. Let’s break down why your initial code was hitting TLE and how the optimized version fixes it.

Why the Original Code Timed Out #

Your first approach relies on repeated substring() calls to generate cyclic shifts of the input string, which is the root of the problem:

• Every substring(1) + substring(0,1) creates two new immutable String objects per iteration. For large values of N (like 10^5 or higher), this leads to O(N²) time and memory overhead—way too slow for large test cases.
• Even though String’s compareTo() is efficient, the constant cost of creating and discarding new strings each cycle adds up quickly, pushing your runtime over the time limit.

The Optimized LinkedList Approach #

The revised code switches to using LinkedList<Character> to handle cyclic shifts, which eliminates the expensive string copying entirely:

• Cyclic shifts are done with inter.add(inter.removeFirst())—an O(1) operation since LinkedList handles head/tail manipulations efficiently, no new objects created here.
• The custom compare() method iterates directly over characters without intermediate strings, keeping the comparison step O(N) but with far lower constant factors.
• We only create a copy of the LinkedList when we find a larger candidate shift, avoiding unnecessary duplication.

Original TLE Code #

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));
            }
        }
    }
}

Optimized Working Code #

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));
            }
        }
    }
}

Extra Tips for Even Better Performance #

If you want to squeeze out more speed (though the current code should pass all test cases), consider:

• Replacing Scanner with BufferedReader for faster input reading—Scanner is convenient but slower for large input sizes.
• Using a custom array-based circular buffer instead of LinkedList. Array access is faster than iterator-based traversal; you can track the start index of the current shift instead of modifying the collection itself.

内容的提问来源于stack exchange，提问作者Abhinav Keshri