Find All Words in the Given Sentence that are Lexicographically Increasing and Lexicographically Decreasing

Saksham Gupta
Last Updated: May 13, 2022

Introduction

You just can’t go to a technical interview without preparing the hot topic, i.e., Strings. Interviews after the interview, we see questions of strings being asked. Thus it’s important to master such a topic. So to help you, your Ninja is here, and today, we will see one such question, i.e., find all words in the given sentence that are lexicographically increasing and lexicographically decreasing. This is more of an application-based question, and you will learn a lot about strings.

Understanding the Problem

We have been given a string ‘S’ representing a sentence. Our task is to find all the words in that string that are lexicographically sorted in increasing order and in decreasing order, along with their counts.

Things will become more clear from the following example

S = “code for us and win a PC”

Now in this example, our output will be

1 “for”
2 “us” “PC”

Explanation:

This is because out of the given input we have only one word that is lexicographically sorted words in increasing order( ‘for’) and we have two words that are sorted in lexographically decreasing order (‘PC’, ‘us’).

Intuition

The intuition is very clear. We will traverse the entire string word by word, and then for each word, we will check if it’s sorted in ascending order or descending order, and then accordingly, we will print them.

We will first count the number of words that are sorted in ascending order and descending order and then will traverse the string again and print them. 

These words will come into play by the following code.

Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

// To check whether the string is sorted in ascending order or not.
bool isAscending(string &s)
{
   // Converting to lowercase so that checking becomes easy.
   transform(s.begin(), s.end(), s.begin(), ::tolower);

   int i = 0;

   while (i < s.length() - 1)
   {
       if (s[i] > s[i + 1])
       {
           return false;
       }
       i++;
   }
   return true;
}

// To check whether the string is sorted in Descending order or not.
bool isDescending(string &s)
{
   // Converting to lowercase so that checking becomes easy.
   transform(s.begin(), s.end(), s.begin(), ::tolower);

   int i = 0;

   while (i < s.length() - 1)
   {
       if (s[i] < s[i + 1])
       {
           return false;
       }
       i++;
   }
   return true;
}

// Function to print lexicographically increasing and decreasing strings.
void printIncSortedDecSorted(string s)
{
   // Creating a stringstream object to split sentence at spaces.
   istringstream temp(s);

   string word;

   // Vectors to store the strings.
   vector<string> lexIncStrings, lexDecStrings;

   // Traversing the string word by Word.
   while (temp >> word)
   {
       if (word.size() <= 1)
           continue;

       // If the word is sorted in ascending order, we will push it in the 'LEX_INC_STRINGS' vector.
       if (isAscending(word))
       {
           lexIncStrings.push_back(word);
       }

       // If the word is sorted in descending order, we will push it in the 'LEX_DEC_STRINGS' vector.
       else if (isDescending(word))
       {
           lexDecStrings.push_back(word);
       }
   }

   // Printing the count of words sorted in ascending order.
   cout << lexIncStrings.size() << " ";

   // Printing the words sorted in ascending order.
   for (string &lexIncString : lexIncStrings)
   {
       cout << lexIncString << " ";
   }

   cout << endl;

   // Printing the count of words sorted in descending order.
   cout << lexDecStrings.size() << " ";

   // Printing the words sorted in ascending order.
   for (string &lexDecString : lexDecStrings)
   {
       cout << lexDecString << " ";
   }
}

int main()
{
   string s;
   getline(cin, s);
   printIncSortedDecSorted(s);

   return 0;
}

Input

“code for us and win a PC”

Output

1 for
2 us PC

Time Complexity

O(N * N), where ‘N’ is the length of the sentence.

As we are traversing the string once and while traversing, we are also checking if the word is sorted in increasing order or decreasing order. Thus time complexity is O(N * N). As in the worst case, the string will be composed of one word only, and in that case, we will be traversing the string twice.

Space Complexity

O(N), where ‘N’ is the length of the sentence.

It is becase we have used stringstream and two vectors which contributes to O(N) size.

Key Takeaways

We saw how we could solve the problem find all words in the given sentence that are lexicographically increasing and lexicographically decreasing. It was more of an application-based question, but we did learn many things. But still, there are many,,, more concepts that you need to brush upon. So what are you waiting for? Head over to our practice platform CodeStudio to practice top problems on every topic, interview experiences, and many more. Till then, Happy Coding!

Was this article helpful ?
0 upvotes