Проверьте, существуют ли лексикографические пифагорейские триплеты в диапазоне [0, K) лексикографически наибольшей строки

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

Дана строка str и положительное целое число K . Задача состоит в том, чтобы найти, существуют ли пифагорейские тройки в первом окне размера K строки, которые имеют те же символы, что и str, но являются наибольшими в лексикографическом порядке .

Примечание. Каждый символ написан в нижнем регистре, и рассмотрите следующие значения для каждого алфавита, чтобы проверить, существуют ли пифагорейские тройки: a = 1, b = 2, . . ., у = 25, z = 26.

A triplet(ch1, ch2, ch3) is called Pythagorean triples if (ch1)2 + (ch2)2 = (ch3)2.

Примеры:

Input: str = “abxczde”, K = 4
Output: NO
Explanation: The lexicographically largest string having the same characters is zxedcba. 
The first window of size 4 is “zxed”, which does not contain any such triplet.

Input: str = “abcdef”, K = 4
Output: YES
Explanation: The lexicographically largest string possible is “fedcba”. 
The first window of size 4 has “fedc” which have a triplet (c, d, e) that is Pythagorean.

Input: str = “dce”, K = 2
Output: NO
Explanation: As window size is less than 3, choosing a triple is not possible.

Подход: Эту проблему можно решить с помощью жадного алгоритма. Выполните следующие шаги для подхода:

  • Отсортировать заданную строку в порядке убывания.
  • В подстроке от 0 до K-1 проверьте, существует ли какая-либо лексикографическая пифагорейская тройка, используя подход с двумя указателями.
  • Если такая тройка найдена, выведите Yes и вернитесь. В противном случае напечатайте No.

Ниже приведена реализация подхода:

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

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