Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition
4.
Code
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Saksham Gupta
0 upvote

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’).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

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!

Previous article
Lexicographically largest String after removal of K characters
Next article
Minimum Count of Inversion Pairs Possible by Concatenating N Binary Strings in any Order
Live masterclass