Question

Write a program that prompts the user to enter a string and displays the maximum consecutive increasingly ordered substring. Analyze the time complexity of your program.

Answer 1

a.

// Program is written in Java Programming Language

// Comments are used for explanatory purpose

// Comments marked x represents simple statements

// Comments marked y represents single loop

// Program starts here

import java.util.*;

public class MaxOrder {

public static void main(String args [] ) {

Scanner accept = new Scanner(System.in);

LinkedList<Character> maxtext = new LinkedList<>();

LinkedList<Character> textlist = new LinkedList<>();

System.out.print("Enter a text: ");

String text = accept.nextLine();

// Find the maximum consecutive increasingly ordered substring

for (int i = 0; i < text.length(); i++) { // y1

if (textlist.size() > 1 && text.charAt(i) <= textlist.getLast() && textlist.contains(text.charAt(i))) {

textlist.clear(); // x

}

textlist.add(text.charAt(i)); // x

if (textlist.size() > maxtext.size()) { // x

maxtext.clear();

maxtext.addAll(list);

}

}

// Display the maximum consecutive

// increasingly ordered substring

for (Character ch: maxtext) { // y2

System.out.print(ch); // x

}

System.out.println();

}

b. Analysing the time complexity

In single loop marked y1, there are 3 simple statements ----- 1

In single loop marked y2, there is 1 simple statement --_--- 2

In (1) above,

1 single loop * 3 simple statements = 3;

*

In (2) above,

1 single loop * 1 simple statement = 1;

So, we have

T(n) = O(n) Linear time