Длина самой длинной подпоследовательности, в которой разница между максимальным и минимальным значением символов ASCII составляет ровно единицу.

Для заданной строки S , состоящей из строчных букв английского алфавита, задача состоит в том, чтобы найти длину самой длинной подпоследовательности из данной строки, чтобы разница между наибольшим и наименьшим значением ASCII была ровно 1 .

Примеры:

Input: S = “acbbebcg”
Output: 5
Explanation: The longest subsequence of required type is “cbbbc”, whose length is 5.
The difference between largest (‘c’) and smallest (‘b’) ASCII values is c – b = 99 – 98 = 1, which is minimum possible.

Input: S = “abcd”
Output: 2
Explanation: The longest subsequence of the required type is “ab”, whose length is 2. Other possible subsequences are “bc” and “cd”.
The difference between largest(‘b’) and smallest(‘a’) ASCII values is b – a = 98 – 97 = 1.

Наивный подход: самый простой подход к решению проблемы состоит в том, чтобы сгенерировать все возможные подпоследовательности заданной строки S и вывести длину подпоследовательности, которая имеет максимальную длину и имеет разность между значениями ASCII наибольшего и наименьшего символа, точно равная 1 .

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

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

• Инициализируйте переменную, скажем, maxLength , которая хранит максимальную длину результирующей подпоследовательности.
• Сохраните частоту символов на карте, скажем, M .
• Пройдитесь по строке и для каждого символа, скажем, ch , проверьте, существует ли символ c со значением ASCII (ch — 1) в карте M или нет. Если окажется, что это правда, то обновите maxLength как максимум maxLength и (M[ch] + M[ch – 1]) .
• После выполнения вышеуказанных шагов выведите в качестве результата значение maxLength .

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

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