Chapter 22, Problem 22.1PE

Program to display maximum consecutive increasingly ordered substring

Program Plan:

• Create the class “Exercise22_01”.
• In the main() function,
  • Read the input object to read the input from user.
  • Call the function maxConsecutivesSortedSubstring()to print the maximum ordered substring.
• In the maxConsecutivesSortedSubstring(),
  • Initially assign the maximum length of the substring.
  • Use for() loop to execute the whole length of the string.
    • Check the position of character at “i” and “i-1” and compare the values.
      • If it is lesser, assign the “i” to “current”.
    • If the condition not satisfies, then increment the length of maximum consecutive length.
    • Use for() loop to iterate the string values.
    • Check whether the current length of string is less than the largest string.
    • If yes, then assign the current element length to largest subsequence element.
    • Construct the character sequence using while() loop at the end of the string.
    • Return the string.
• In the maxConsecutivesSortedSubstring1(),
  • Use the for loop to iterate the whole length of string.
    • Check the position of character at “i” and “i-1” and compare the values.
    • Return the sorted substring.

This program reads the input from user and displays the maximum consecutive increasingly ordered substring.

Program:

//Declare the class Exercise22_01

public class Exercise22_01 {

       //Declare the main function

       public static void main(String[] args) {

          //Create the input object

           java.util.Scanner input = new

           java.util.Scanner(System.in);

          //Read the string

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

          String s = input.nextLine();

          /*Call the function maxConsecutiveSortedSubstring() to print the maximum consecutive sorted substring*/

          System.out.println("Maximum consecutive substring

            is " + maxConsecutiveSortedSubstring(s));

        }

        /*Define the function maxConsecutiveSortedSubstring()*/

        public static String

            maxConsecutiveSortedSubstring(String s) {

          //Declare the array and assign the length of array

          int[] maxConsecutiveLength = new int[s.length()];

          //Assign the variable as 0

          int current = 0;

          //Execute the for loop until the condition fails

          for (int i = 1; i < s.length(); i++) {

             /*Check whether the character is smaller than 

             the current character stored in string*/

            if (s.charAt(i) <= s.charAt(i - 1)) {

             //Assign the “i” value to current variable

             current = i;

           } else {

             /*Execute the for loop until the condition fails*/

             for (int j = i - 1; j >= current; j--)

             //Increment the sequence of length

               maxConsecutiveLength[j]++;

           }

         }

         //Assign the length of sequence at index “i”

         int currentMaxLength = maxConsecutiveLength[0];

         int index = 0;

         //Execute the for loop until the length of string

         for (int i = 0; i < s.length(); i++) {

             //Check whether the condition is true

             if (maxConsecutiveLength[i] > currentMaxLength)

             {

                /*Assign the maximum sequence length to current length */

                currentMaxLength = maxConsecutiveLength[i];

                //Assign the index position

                index = i;

           }

         }

         //Return the substring

         return s.substring(index, index + currentMaxLength + 1);

       }

     //Define the function for the sorted substring

     public static String

     maxConsecutiveSortedSubstring1(String s) {

          //Assign the current length

          int currentMaxLength = 1;

          //Assign the last index of sorted substring

          int lastIndexOfMaxConsecutiveSortedSubstring = 0;

          //Assign the possible length

          int possibleMaxLength = 1;

          //Execute the for loop until it fails

          for (int i = 1; i < s.length(); i++) {

               //Check the position of the string

               if (s.charAt(i) > s.charAt(i - 1)) {

                    //Check the condition

                    if

                    (lastIndexOfMaxConsecutiveSortedSubstri

                    ng == i - 1) {

                         /* Add the max consecutive substring*/

                         currentMaxLength++;

                         /*Add the index of max consecutive substring*/

                         lastIndexOfMaxConsecutiveSortedSub

                         string++;

                    //If condition not satisfies

                    } else {

                         //Increment the length

                         possibleMaxLength++;

                         //Check the condition

                         if (possibleMaxLength >

                         currentMaxLength) {

                              /*Assign the possible length to current maximum length*/

                              currentMaxLength =

                              possibleMaxLength;

                              /*Assign the index of the string*/

                              lastIndexOfMaxConsecutiveSort

                              edSubstring = i;

                              possibleMaxLength = 1;

                         }

                    }

               }

          }

          //Return the sorted substring

          return

          s.substring(lastIndexOfMaxConsecutiveSortedSubstr

          ing - currentMaxLength + 1,lastIndexOfMaxConsecutiveSortedSubstring + 1);

     }

}

Running time complexity:

The above program executes in $\text{Ο}\left({\text{n}}^{\text{2}}\right)$ because the loop gets iterated two times consecutively to determine the length of the string. Therefore, the running time is $\text{Ο}\left({\text{n}}^{\text{2}}\right)$.

Sample Output:

Enter a string: abcabcdgabmnsxy

Maximum consecutive substring is abmnsxy

Program Plan Intro

Program to display maximum consecutive increasingly ordered substring

Program Plan:

• Create the class “Exercise22_01”.
• In the main() function,
  • Read the input object to read the input from user.
  • Call the function maxConsecutivesSortedSubstring()to print the maximum ordered substring.
• In the maxConsecutivesSortedSubstring(),
  • Initially assign the maximum length of the substring.
  • Use for() loop to execute the whole length of the string.
    • Check the position of character at “i” and “i-1” and compare the values.
      • If it is lesser, assign the “i” to “current”.
    • If the condition not satisfies, then increment the length of maximum consecutive length.
    • Use for() loop to iterate the string values.
    • Check whether the current length of string is less than the largest string.
    • If yes, then assign the current element length to largest subsequence element.
    • Construct the character sequence using while() loop at the end of the string.
    • Return the string.
• In the maxConsecutivesSortedSubstring1(),
  • Use the for loop to iterate the whole length of string.
    • Check the position of character at “i” and “i-1” and compare the values.
    • Return the sorted substring.

Program Description Answer

This program reads the input from user and displays the maximum consecutive increasingly ordered substring.

Explanation of Solution

Program:

//Declare the class Exercise22_01

public class Exercise22_01 {

  //Declare the main function

  public static void main(String[] args) {

     //Create the input object

java.util.Scanner input = new

java.util.Scanner(System.in);

    //Read the string

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

    String s = input.nextLine();

/*Call the function maxConsecutiveSortedSubstring() to print the maximum consecutive sorted substring*/

    System.out.println("Maximum consecutive substring

is " + maxConsecutiveSortedSubstring(s));

  }

/*Define the function maxConsecutiveSortedSubstring()*/

  public static String

maxConsecutiveSortedSubstring(String s) {

    //Declare the array and assign the length of array

    int[] maxConsecutiveLength = new int[s.length()];

    //Assign the variable as 0

    int current = 0;

    //Execute the for loop until the condition fails

    for (int i = 1; i < s.length(); i++) {

/*Check whether the character is smaller than 

the current character stored in string*/

      if (s.charAt(i) <= s.charAt(i - 1)) {

   //Assign the “i” value to current variable

        current = i;

      } else {

/*Execute the for loop until the condition fails*/

        for (int j = i - 1; j >= current; j--)

//Increment the sequence of length

          maxConsecutiveLength[j]++;

      }

    }

    //Assign the length of sequence at index “i”

    int currentMaxLength = maxConsecutiveLength[0];

    int index = 0;

    //Execute the for loop until the length of string

    for (int i = 0; i < s.length(); i++) {

 //Check whether the condition is true

      if (maxConsecutiveLength[i] > currentMaxLength)

 {

/*Assign the maximum sequence length to current length */

        currentMaxLength = maxConsecutiveLength[i];

   //Assign the index position

        index = i;

      }

    }

    //Return the substring

return s.substring(index, index + currentMaxLength + 1);

  }

//Define the function for the sorted substring

public static String

maxConsecutiveSortedSubstring1(String s) {

//Assign the current length

int currentMaxLength = 1;

//Assign the last index of sorted substring

int lastIndexOfMaxConsecutiveSortedSubstring = 0;

//Assign the possible length

int possibleMaxLength = 1;

//Execute the for loop until it fails

for (int i = 1; i < s.length(); i++) {

//Check the position of the string

if (s.charAt(i) > s.charAt(i - 1)) {

//Check the condition

if

(lastIndexOfMaxConsecutiveSortedSubstri

ng == i - 1) {

/* Add the max consecutive substring*/

currentMaxLength++;

/*Add the index of max consecutive substring*/

lastIndexOfMaxConsecutiveSortedSub

string++;

//If condition not satisfies

} else {

//Increment the length

possibleMaxLength++;

//Check the condition

if (possibleMaxLength >

currentMaxLength) {

/*Assign the possible length to current maximum length*/

currentMaxLength =

possibleMaxLength;

/*Assign the index of the string*/

lastIndexOfMaxConsecutiveSort

edSubstring = i;

possibleMaxLength = 1;

}

}

}

}

//Return the sorted substring

return

s.substring(lastIndexOfMaxConsecutiveSortedSubstr

ing - currentMaxLength + 1,lastIndexOfMaxConsecutiveSortedSubstring + 1);

}

}

Running time complexity:

The above program executes in $\text{Ο}\left({\text{n}}^{\text{2}}\right)$ because the loop gets iterated two times consecutively to determine the length of the string. Therefore, the running time

is $\text{Ο}\left({\text{n}}^{\text{2}}\right)$.

Sample Output

Enter a string: abcabcdgabmnsxy

Maximum consecutive substring is abmnsxy