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