Given a string representing a sentence named str of size N, the task is to find all the valid words in a sentence that are lexicographically sorted in increasing order and in decreasing order along with their counts.
Note: Valid words are:-
- words don’t containing numbers.
- words greater than size 1.
Examples:
Input: str=”neveropen for neveropen”
Output:
1 “for”
0
Explanation: “for” is word which is lexicographically sorted in increasing order(1). There is no word which lexicographically sorted in decreasing order(0).Input: str=”We won the match by 4 runs”
Output:
1 “by”
3 “we”, “won”, “the”
Explanation: “by” is sorted in increasing order(1) whereas “we”, “won” and “the” are lexicographically sorted in decreasing order(3).
Approach: The idea to traverse the string word by word and check for each word if it is lexicographically increasing or lexicographically decreasing. Print each word based on the type found.
Follow the below steps to know about the approach in detail:
- First traverse the words in a given string and count the number of lexicographically increasing and lexicographically decreasing words, in count1 and count2 respectively.
- Now first print the count of lexicographically increasing words stored in count1
- Then traverse the string again word by word and print all lexicographically increasing words.
- Repeat the last two steps for lexicographically decreasing words.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if string is// sorted in increasing orderbool issorted(string s){ // using transform() function and ::tolower in STL transform(s.begin(), s.end(), s.begin(), ::tolower); for (int i = 0; i < s.size() - 1; i++) { if (s[i] > s[i + 1] or isdigit(s[i])) { return false; } } return true;}// Function to check ifstring is// sorted in decreasing orderbool issortedre(string s){ // using transform() function and ::tolower in STL transform(s.begin(), s.end(), s.begin(), ::tolower); for (int i = 0; i < s.size() - 1; i++) { if (s[i] < s[i + 1] or isdigit(s[i])) { return false; } } return true;}// Function to count// the required absolute differencevoid count(string s){ stringstream ss(s); string word; int count1 = 0, count2 = 0; // Checking validity of word while (ss >> word) { if (word.size() == 1) continue; // Counting the valid words // in increasing order if (issorted(word)) { count1++; } // Counting the valid words // in decreasing order else if (issortedre(word)) { count2++; } } stringstream ss1(s); // Printing count of // lexicographically increasing words cout << count1 << " "; // Print all lexicographically // increasing words while (ss1 >> word) { if (word.size() == 1) continue; // Printing all valid words // in increasing order if (issorted(word)) { cout << "\"" << word << "\" "; } } cout << endl; stringstream ss2(s); // Printing count of // lexicographically increasing words cout << count2 << " "; // Print all lexicographically // increasing words while (ss2 >> word) { if (word.size() == 1) continue; // Printing all valid words // in decreasing order else if (issortedre(word)) { cout << "\"" << word << "\" "; } } cout << endl;}// Driver Codeint main(){ string s = "We won the match by 4 runs"; count(s); return 0;} |
Java
// Java program for the above approachclass GFG { static boolean isdigit(char c) { return c >= '0' && c <= '9'; } // Function to check if String is // sorted in increasing order public static boolean issorted(String s) { // using transform() function and ::tolower in STL s = s.toLowerCase(); for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) > s.charAt(i + 1) || isdigit(s.charAt(i))) { return false; } } return true; } // Function to check ifString is // sorted in decreasing order public static boolean issortedre(String s) { // using transform() function and ::tolower in STL s = s.toLowerCase(); for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) < s.charAt(i + 1) || isdigit(s.charAt(i))) { return false; } } return true; } // Function to count // the required absolute difference public static void count(String s) { String[] ss = s.split(" "); String word; int count1 = 0, count2 = 0; // Checking validity of word for (int i = 0; i < ss.length; i++) { word = ss[i]; if (word.length() == 1) continue; // Counting the valid words // in increasing order if (issorted(word)) { count1++; } // Counting the valid words // in decreasing order else if (issortedre(word)) { count2++; } } String[] ss1 = s.split(" "); // Printing count of // lexicographically increasing words System.out.print(count1 + " "); // Print all lexicographically // increasing words for (int i = 0; i < ss1.length; i++) { word = ss1[i]; if (word.length() == 1) continue; // Printing all valid words // in increasing order if (issorted(word)) { System.out.print("\"" + word + "\" "); } } System.out.println(); String[] ss2 = s.split(" "); // Printing count of // lexicographically increasing words System.out.print(count2 + " "); // Print all lexicographically // increasing words for (int i = 0; i < ss2.length; i++) { word = ss2[i]; if (word.length() == 1) continue; // Printing all valid words // in decreasing order else if (issortedre(word)) { System.out.print("\"" + word + "\" "); } } System.out.println(); } // Driver Code public static void main(String args[]) { String s = "We won the match by 4 runs"; count(s); }}// This code is contributed by gfgking. |
Python3
# Python Program to implement# the above approachdef isCharNumber(c): return c >= '0' and c <= '9'# Function to check if string is# sorted in increasing orderdef issorted(s): # using transform() function and ::tolower in STL s = s.lower() for i in range(len(s) - 1): if (ord(s[i]) > ord(s[i + 1]) or isCharNumber(s[i])): return False return True# Function to check ifstring is# sorted in decreasing orderdef issortedre(s): # using transform() function and ::tolower in STL s = s.lower() for i in range(len(s) - 1): if (ord(s[i]) < ord(s[i + 1]) or isCharNumber(s[i])): return False return True# Function to count# the required absolute differencedef count(s): word = "" count1 = 0 count2 = 0 ss = s.split(" ") # Checking validity of word for i in range(len(ss)): word = ss[i] if (len(word) == 1): continue # Counting the valid words # in increasing order if (issorted(word)): count1 += 1 # Counting the valid words # in decreasing order elif (issortedre(word)): count2 += 1 # Printing count of # lexicographically increasing words print(count1, end=" ") # Print all lexicographically # increasing words for i in range(len(ss)): word = ss[i] if (len(word) == 1): continue # Printing all valid words # in increasing order if (issorted(word)): print(f" {word} ") # Printing count of # lexicographically increasing words print(count2, end=" ") # Print all lexicographically # increasing words for i in range(len(ss)): word = ss[i] if (len(word) == 1): continue # Printing all valid words # in decreasing order elif (issortedre(word)): print(f" {word} ", end=" ") # Driver Codes = "We won the match by 4 runs"count(s)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{static bool isdigit(char c) { return c >= '0' && c <= '9';}// Function to check if String is// sorted in increasing orderpublic static bool issorted(String s) { // Using transform() function and ::tolower in STL s = s.ToLower(); for(int i = 0; i < s.Length - 1; i++) { if (s[i] > s[i + 1] || isdigit(s[i])) { return false; } } return true;}// Function to check ifString is// sorted in decreasing orderpublic static bool issortedre(String s){ // Using transform() function and ::tolower in STL s = s.ToLower(); for(int i = 0; i < s.Length - 1; i++) { if (s[i] < s[i + 1] || isdigit(s[i])) { return false; } } return true;}// Function to count the// required absolute differencepublic static void count(String s){ String[] ss = s.Split(' '); String word; int count1 = 0, count2 = 0; // Checking validity of word for(int i = 0; i < ss.Length; i++) { word = ss[i]; if (word.Length == 1) continue; // Counting the valid words // in increasing order if (issorted(word)) { count1++; } // Counting the valid words // in decreasing order else if (issortedre(word)) { count2++; } } String[] ss1 = s.Split(' '); // Printing count of lexicographically // increasing words Console.Write(count1 + " "); // Print all lexicographically // increasing words for(int i = 0; i < ss1.Length; i++) { word = ss1[i]; if (word.Length == 1) continue; // Printing all valid words // in increasing order if (issorted(word)) { Console.Write("\"" + word + "\" "); } } Console.WriteLine(); String[] ss2 = s.Split(' '); // Printing count of lexicographically // increasing words Console.Write(count2 + " "); // Print all lexicographically // increasing words for(int i = 0; i < ss2.Length; i++) { word = ss2[i]; if (word.Length == 1) continue; // Printing all valid words // in decreasing order else if (issortedre(word)) { Console.Write("\"" + word + "\" "); } } Console.WriteLine();}// Driver Codepublic static void Main(String []args) { String s = "We won the match by 4 runs"; count(s);}}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach function isCharNumber(c) { return c >= '0' && c <= '9'; } // Function to check if string is // sorted in increasing order function issorted(s) { // using transform() function and ::tolower in STL s = s.toLowerCase() for (let i = 0; i < s.length - 1; i++) { if (s[i].charCodeAt(0) > s[i + 1].charCodeAt(0) || isCharNumber(s[i])) { return false; } } return true; } // Function to check ifstring is // sorted in decreasing order function issortedre(s) { // using transform() function and ::tolower in STL s = s.toLowerCase(); for (let i = 0; i < s.length - 1; i++) { if (s[i].charCodeAt(0) < s[i + 1].charCodeAt(0) || isCharNumber(s[i])) { return false; } } return true; } // Function to count // the required absolute difference function count(s) { let word; let count1 = 0, count2 = 0; let ss = s.split(" "); // Checking validity of word for (let i = 0; i < ss.length; i++) { word = ss[i] if (word.length == 1) continue; // Counting the valid words // in increasing order if (issorted(word)) { count1++; } // Counting the valid words // in decreasing order else if (issortedre(word)) { count2++; } } // Printing count of // lexicographically increasing words document.write(count1 + " "); // Print all lexicographically // increasing words for (let i = 0; i < ss.length; i++) { word = ss[i]; if (word.length == 1) continue; // Printing all valid words // in increasing order if (issorted(word)) { document.write(" " + word + " ") } } document.write('<br>'); // Printing count of // lexicographically increasing words document.write(count2 + " "); // Print all lexicographically // increasing words for (let i = 0; i < ss.length; i++) { word = ss[i]; if (word.length == 1) continue; // Printing all valid words // in decreasing order else if (issortedre(word)) { document.write(" " + word + " ") } } document.write('<br>'); } // Driver Code let s = "We won the match by 4 runs"; count(s); // This code is contributed by Potta Lokesh </script> |
Output:
1 "by" 3 "We" "won" "the"
Time Complexity: O(N^2), as we are using nested loops for traversing N*N times.
Auxiliary Space: O(N), as we are using extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
