Количество возрастающих подстрок в заданной строке

Опубликовано: 21 Сентября, 2022

Для заданной строки str длины N задача состоит в том, чтобы напечатать количество подстрок, в которых значение ASCII каждого символа больше или равно значению ASCII предыдущего символа. Подстроки должны иметь длину не менее 2.

Пример :

Input: str = “bcdabc”
Output: 6
Explanation: The 6 substrings with alphabets having greater ASCII value than the previous character and length at least 2 are bc, bcd, cd, ab, abc, bc 

Input: str = “cegxza”
Output: 10

Наивный подход . Вышеупомянутая проблема может заключаться в повторении строки и подсчете возрастающих подстрок значений ASCII, начиная с каждого индекса.
Временная сложность: O(N^2)

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

  • Инициализировать указатели слева и справа до 0
  • Инициализировать переменную и сохранить ответ
  • Итерировать строку до тех пор, пока правый указатель не станет меньше длины строки:
    • Используйте цикл while для итерации с использованием правого указателя до тех пор, пока str[right] >= str[right – 1] и right < str.length()
    • Рассчитайте количество подстрок, имеющих увеличивающееся значение ASCII, добавив инициализацию len = right – left, а затем добавив значение (len * (len + 1)/2) – len к an
    • Сделайте левый = правый , и правый указатель будет увеличиваться для следующей итерации.
  • Вернуть ответ как наш результат

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ