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

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.

Edited 6 Years Ago by verruckt24: n/a

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.

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

Attachments
public class Algorithm23_1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

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.

This article has been dead for over six months. Start a new discussion instead.