Самая длинная подстрока заданных символов путем замены не более K символов для Q запросов

Опубликовано: 27 Февраля, 2023

Для заданной строки s длины N и Q запросов, каждый из которых имеет тип (K, C), где K — целое число C — символ, задача состоит в том, чтобы заменить не более K символов строки на C и вывести максимальное количество длина возможной подстроки, содержащей только символ C .

Примеры :

Input: s = “yamatonadeshiko”, N = 15, Q = 10,  
queries[] = {{1, a}, {2, a}, {3, a}, {4, a}, {5, a}, {1, b}, {2, b}, {3, b}, {4, b}, {5, b}}
Output: 3, 4, 5, 7, 8, 1, 2, 3, 4, 5
Explanation: In the first query “ama” can be made “aaa” by 1 replacement 
In the second query “yama” can be made “aaaa” so answer is 4
In the third query “yamat” can be made “aaaaa” so answer is 5
In the 4th query “amatona” can be made “aaaaaaa” so answer is 7 
In the 5th query “yamatona” can be made “aaaaaaaa” so answer is 8
In the 6th query since there is no b any character say “y” can be made “b” 
In the 7th query  “ya” can be made “bb” 
In the 8th query “yam” can be made “bbb” 
In the 9th query “yama” can be made “bbbb”
In the 10th query “yamat” can be made “bbbbb” 

Input: s = “koyomi”, N = 6, Q = 3, queries[] = {{1, o}, {4, o}, {4, m}}
Output: 3, 6, 5
Explanation : In the first query “oyo”  can be made “ooo” using 1 replacement.
In the second query  “koyomi”  can be made “ooooo”.
In the third query “koyom” can be made “mmmmm” using 4 replacement “koyo”.

Подход: Идея эффективного решения этой проблемы основана на концепции динамического программирования:

If we can find out the longest substring of character ‘ch‘ till ith index by performing j replacements, we can easily find the longest substring of character ch till (i+1)th index by performing j replacements. There are two cases: 

  1. ith character and ch are same and 
  2. They are different.

If this is expressed mathematically as a function we can write it as f(ch, i, j). So the length in the two cases will be:

  1. As they are same so the length will be one more than it was till ith with j changes. So f(ch, i, j) = f(ch, i-1, j) + 1
  2. As they are different, the length will be one more than it was till ith index with j-1 changes. So f(ch, i, j) = f(ch, i-1, j-1) + 1

So for at most K changes by character C, it is the maximum of all the longest substring till any index for any number of changes in the range [1, K].

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Предварительно вычислите результат, используя динамическое программирование и отношение, как указано выше .
  • Создайте трехмерный массив dp[][][] для хранения результата предварительного вычисления.
  • Предварительно вычислите результат для любого количества изменений для любого символа, чтобы ответить на запросы за линейное время:
    • Если ответ для ch с почти K изменениями представлен в виде g(K, ch), то он является максимальным из всех значений f(ch, i, K) , где i изменяется от (0 до N-1).
    • Используйте другой двумерный массив (скажем, ans[][] ) для хранения результата g(K, ch) .
  • Пройдитесь по запросам и найдите значение из массива ans[][] .

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

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

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