Checks whether a string can be made lexicographically smaller by reversing any substring

In C, we have a built-in reverse() function for reversing a substring to check if a string can become smaller lexicographically. Dictionary ordering is the process of sorting the characters of a word into dictionary order.

Let us take a string example to check whether the lexicographic order is smaller.

• We will compare these two words to check for the lexicographically smaller word and take two strings, 'apple' and 'army'. The first letter of both strings begins with the letters ‘a’. When we examine the second character of the two letters, alphabetically, ‘p’ comes before ‘r’. Therefore, lexicographically, apple is smaller than army.

• In the string "tutorialspoint", reverse the substring "oria" to get "airo", the substring Smaller in lexicographic order. Then write the final string as "tutairolspoint".

• In the string "tutorix", reverse the substring "tori" to get "irot", because the first The starting character of the substring is 't', and the second substring is 'i', so 'i' is located at # in the alphabet before ##'t', so 'irot' is lexicographically smaller than 'tori'. The final string is written "tuirotx"

We will take another string example, such as

"acwz".

grammar

reverse( str_name.begin(), str_name.end() )

illustrate

The reverse function is part of the C standard library. It accepts two parameters

"str_name.begin()" and "str_name.end()".

• str_name is a user-suggested string name.

• begin() and end() are predefined built-in functions used under the reverse function. The job of the begin function is to return an iterator pointing to the first character of the input string. The end function returns an iterator that points to a position before the last character of the input string.

Please note that the reverse function will not return anything because it directly modifies the container (str_name).

algorithm

First, we will use the three necessary header files, namely iostream, string and include

• We will start in the main function where we declare a string variable named

  'str' and store the string 'tutorialspoint' in it. We will then declare the boolean variable 'isReverse' as 'false' to indicate that the given string has not been reversed and is still in its original form.

• We will then create two nested for loops to check every possible substring of

  'str'. The substring is then stored in a temporary string named 'temp'.

• Afterwards, we call the

  'reverse()' function to reverse the substring stored in the 'temp' variable between index 'i' and String 'j'.

• Later create an if statement to check if the reversed string is lexicographically less than the variables

  'temp' and 'str' are compared.

• The compiler will compare the variables temp and str. If they are both equal, then the variable

  'isReverse' will be set to true and it will break the if statement.

• Now, we check the value of isReverse and if it is true, print the if conditional statement, otherwise print the else conditional statement.

• exit the program.

Example

In this program we will see how to make a string lexicographically smaller by reversing any substring.

#include <iostream>
#include <string>
#include <algorithm> 
using namespace std;
int main() {
   string str = "tutorialspoint";
   // User can change this to test other strings such as acwz, groffer, etc
   bool isReverse = false; // it is used to indicate whether or not a substring has been found in the original string “str”.


   // use the loop through all possible substrings of str
   for (int i = 0; i < str.length(); i++) {
      for (int j = i+1; j < str.length(); j++) {
         string temp = str; 
         // create new temporary variable to store the value of str.
         // reverse the substring of i and j
         reverse ( temp.begin() + i, temp.begin() + j + 1 ); 
         // reverse function follow the header file name as <algorithm>
         if (temp < str) { 
            // Check whether the reversed string is lexicographically smaller
            isReverse = true;
            break;
         }
      }
   }
   if ( isReverse ) {
      cout << "Yes, this is lexicographically smaller by reversing a  substring." << endl;
   } else {
      cout << "No, this is not lexicographically smaller by reversing a substring." << endl;
   }
   return 0;
}

Output

If we enter the value "tutorialspoint" we will get the following results -

Yes, this is lexicographically smaller by reversing a  substring.

If we enter the value "acwz" we will get the following results:

No, this is not lexicographically smaller by reversing a substring.

in conclusion

We saw how to use string variables to calculate the smaller value in a dictionary by reversing any substring. Then we set the string variable to a temporary variable. We then use the predefined function "reverse()" to calculate the dictionary words in their reverse form. Next, we check the lexicographically smaller one by comparing the variables temp and str and get the result.

The above is the detailed content of Checks whether a string can be made lexicographically smaller by reversing any substring. For more information, please follow other related articles on the PHP Chinese website!