Проверьте, существуют ли лексикографические пифагорейские триплеты в диапазоне [0, K) лексикографически наибольшей строки
Дана строка 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)