CODEWITHSUNDEEP
javastringperformancecharacter
bpjoshi
bpjoshi

Reputation: 1141

What is the fastest way to compare alternate characters of a string using java?

There are multiple strings being passed to this program from standard input. The first int input T, is the number of test cases(Strings) being passed to this program. A string which has different alternate characters is perfect. If alternate characters are the same, you have need to delete 1 of those two characters. Basically, you have to count, how many characters, do you need to delete to get a perfect String? For example: ABABAB is pefect while AABABAA is not perfect. You need to delete 2 A's, the first one and the last one.In AAAA, you need to delete 3 A's to get a perfect string. String input can be very large. What is the fastest way to count number of such deletion? The code below, written by me, is working very slow.

public static void main(String[] args) {
    Scanner scan = new Scanner (System.in);
    int T= scan.nextInt();
    String str;
    int count=0;
    for(int i=0; i<T; i++){
        str=scan.next();
        for(int j=0; j<str.length()-1; j++){
            if(str.charAt(j)!=str.charAt(j+1)){
                j+=2;
            }
            else{
                count++;
            }
        }
        System.out.println(count);
    }
}

Upvotes: 0

Views: 1521

Answers (2)

bpjoshi
bpjoshi

Reputation: 1141

This is my working code after eliminating all the logical errors. For some test cases its execution time is up to 0.45-0.50 seconds. Can its performance be improved?

public static void main(String[] args) {
    int T=0; String str;
    Scanner sc = new Scanner(System.in);
    T=sc.nextInt();
    for(int i=0; i<T; i++){
       str= sc.next();
       solve(str);
    }
}
public static void solve(String str){
    char first, second; int count=0;
    for(int i=0; i<str.length()-1; i++){
       first= str.charAt(i);
       second= str.charAt(i+1);
       if(first==second){
           count++;
       }
    }
    System.out.println(count);
}

Upvotes: 0

Hoopje
Hoopje

Reputation: 12942

Before you worry about the performance, worry about whether your solution is correct. For the input ABAAB, your program returns 0, however 1 A must be removed to obtain a perfect string.

Then: what do you mean with "very large". How many characters is that? And what is "very slow"?

You will have to look at every character of the string at least once, so you will not get much faster. However, you might be able to optimize a bit. At the moment, it is possible that you look at a single character twice (once in str.charAt(j+1) and in the next iteration in str.charAt(j)). It is certainly possible to write your algorithm in such a way that every character of the string is visited exactly once. But again, you should focus on correctness before you focus on speed.

Upvotes: 1

Related Questions