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;
}
You can also try this code with Online C++ Compiler
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.
Also check out - Inorder Predecessor, and Euclid GCD Algorithm
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 Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. Till then, Happy Coding!
568+ registered 
