Algorithm to find the maximum consecutive sorted substring

[selenask]

Hi, Im suppose to write a Maximum consecutive sorted substring in a string. "abacdefkabfh" is acdefk. Im suppose to analyze the time omplexity of an algorithm.. I dont know where to begin

[verruckt24]

Google.

[verruckt24]

Alright, no one's come up with help as of now so I proceed forward.

What you could do is move through the entire string character by character, everytime comparing whether current character is greater than the previous one. 'Greater than' means that the character comes later in the alphabet than the previous one. This could be done simply by doing something like this:

seqStr=str.chaAt(i); // add the first character directly to the sorted string sequence.
for(int i=0;i<str.length();i++){
    if (str.charAt(i)<str.charAt(i+1){
        //concat the char at i+1 to the sorted substring sequence
        seqStr+=str.charAt(i+1); 
    }
    if (seqStr.length()>maxSeq){
        maxSeqStr=seqStr;
    }
}

If you work on these lines then by the time you are done traversing the string, you would have your longest sorted substring sequence ready. You would have to add a lot more into this code to get it working, this is just an outline of the critical part.

[selenask]

thanks, but this is what I could sort of fix, can you help me with the rest.

public class Algorithm23_1 {
public static void main(String[] args) {
String str;
char seqStr;

seqStr=str.charAt(0); // add the first character directly to the sorted string sequence.
for(int i=0;i<str.length();i++){
if (str.charAt(i)<str.charAt(i+1){
//concat the char at i+1 to the sorted substring sequence
//seqStr+=str.charAt(i+1);
}
if ( seqStr.length()>maxSeq){
maxSeqStr=seqStr;
}
}

}

}

Alright, no one's come up with help as of now so I proceed forward.

What you could do is move through the entire string character by character, everytime comparing whether current character is greater than the previous one. 'Greater than' means that the character comes later in the alphabet than the previous one. This could be done simply by doing something like this:

seqStr=str.chaAt(i); // add the first character directly to the sorted string sequence.
for(int i=0;i<str.length();i++){
    if (str.charAt(i)<str.charAt(i+1){
        //concat the char at i+1 to the sorted substring sequence
        seqStr+=str.charAt(i+1); 
    }
    if (seqStr.length()>maxSeq){
        maxSeqStr=seqStr;
    }
}

If you work on these lines then by the time you are done traversing the string, you would have your longest sorted substring sequence ready. You would have to add a lot more into this code to get it working, this is just an outline of the critical part.

[selenask]

edited

Hi, Im suppose to write a Maximum consecutive sorted substring in a string. "abacdefkabfh" is acdefk. Im suppose to analyze the time omplexity of an algorithm.. I dont know where to begin

[BestJewSinceJC]

Complexity should be O(n). You only need to scan through the entire String once. If you get to a point where your current sequence it is no longer in sorter order, start your current counter over, moving to the next character. Then repeat.