CODEWITHSUNDEEP
javaalgorithm
Himanshu
Himanshu

Reputation: 3970

How to Optimise a given problem time complexity?

I have a question which says

Given an input 

ababacad

The output should be all the a's should come first together rest characters should follow their sequence as they were originally. i.e.

aaaabbcd

I solved it like below code

String temp="", first="" ;

for(int i=0;i<str.length;i++) {
  if(str.charAt(i)!='a')
    temp=temp+str.charAt(i);
  else
    first=first+str.charAt(i);
} 

System.out.print(first+temp);

The output matches but it says it is still not optimised. I guess its already order of N complexity. Can it be optimised further.

Upvotes: 1

Views: 143

Answers (1)

kumarchandresh
kumarchandresh

Reputation: 590

Optimization here can mean string operations as well as the number of iterations. So, just to be on the safe side, you can implement it using arrays. The time complexity will be O(n) which is the minimum for this problem as you have to check every position for the presence of char 'a'.

String input = "ababacad";

char[] array = input.toCharArray();
char[] modified = new char[array.length];

int a = 0; // index for a
int b = array.length - 1; // index for not a

for (int i = array.length - 1; i >= 0; --i) {
    if (array[i] != 'a')
        modified[b--] = array[i];
    else
        modified[a++] = array[i];
}

String output = new String(modified);
System.out.println(output);

Upvotes: 1

Related Questions