Самая длинная подпоследовательность с тем же символом, что и подстроки, и разницей в частоте не более K

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

• Частота каждой буквы в подпоследовательности не отличается более чем на K от частоты любой другой буквы.
• Для любой буквы L , которая появляется хотя бы один раз, все вхождения L должны образовывать непрерывный сегмент.

Примеры:

Input: S = “abba” , K = 1
Output: 3
Explanation: Subsequence “abb” and “bba” satisfies both the conditions.

Input: S = “aaa” , K = 2
Output: 3

Наивный подход: чтобы решить проблему, следуйте следующей идее:

The brute force approach is to generate all subsequences and then check whether it meets all the conditions or not.

Выполните указанные шаги, чтобы решить данную проблему:

• Сгенерировать все подпоследовательности для данной строки.
• Если длина подпоследовательности больше 0 , то проверьте, являются ли одинаковые символы непрерывными или нет (реализовано как функция isContinuous ).
• Снова проверьте, меньше ли разница между максимальной частотой и минимальной частотой k или нет.
• Если предыдущие два шага пройдены, то сохраните максимальную длину всех таких подпоследовательностей. (скажем, maxLen ).
• Верните максимальную длину maxLen в качестве окончательного ответа.

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