Найдите все слова в данном предложении, которые лексикографически возрастают и лексикографически убывают

Учитывая строку, представляющую предложение с именем str размера N , задача состоит в том, чтобы найти все допустимые слова в предложении, которые лексикографически отсортированы в порядке возрастания и в порядке убывания вместе с их количеством.

Note: Valid words are:-

• words don’t containing numbers.
• words greater than size 1.

Примеры:

Input: str=”geeks for geeks”
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).

Подход: Идея пройти по строке слово за словом и проверить для каждого слова, является ли оно лексикографически возрастающим или лексикографически убывающим. Выведите каждое слово в зависимости от найденного типа.

Выполните следующие шаги, чтобы узнать о подходе в деталях:

• Сначала просмотрите слова в заданной строке и подсчитайте количество лексикографически увеличивающихся и лексикографически убывающих слов в count1 и count2 соответственно.
• Теперь сначала выведите количество лексикографически увеличивающихся слов, хранящихся в count1.
• Затем снова пройдитесь по строке слово за словом и выведите все лексикографически возрастающие слова.
• Повторите последние два шага для лексикографически убывающих слов.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N^2), так как мы используем вложенные циклы для прохождения N*N раз.
Вспомогательное пространство: O(N), так как мы используем дополнительное пространство.