Самая длинная общая подпоследовательность без повторяющихся символов

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

Имея две строки s1 и s2 , задача состоит в том, чтобы найти длину самой длинной общей подпоследовательности без повторяющихся символов.

Примеры:

Input: s1= “aabbcc”, s2= “aabc”
Output: 3
Explanation: “aabc” is longest common subsequence but it has two repeating character ‘a’.
So the required longest common subsequence with no repeating character is “abc”.

Input: s1=  “aabcad”,  s2= “adbcwcad”
Output: 4
Explanation: The subsequences are “abcd” or “bcad”.

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

  • Для каждого символа в i -й позиции этот символ может быть частью последовательности или нет.
  • Таким образом сгенерируйте каждую последовательность и проверьте наличие самой длинной общей последовательности.
  • Чтобы отслеживать, какие символы включены в подпоследовательность, используйте биты переменной «store» .
  • Каждый бит переменной store указывает, присутствует ли этот алфавит в подпоследовательности или нет.
  • бит в 0-й позиции соответствует символу 'a', в позиции 1 соответствует 'b', аналогично 2 - 'c' и т.д.

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(N * 2 N ), где N максимально (размер s1, размер s2).
Вспомогательное пространство: O(1)

Эффективный подход. Эффективный подход заключается в использовании мемоизации для уменьшения временной сложности. Создайте двумерный массив dp[][], где dp[i][j] хранит длину самой длинной общей подпоследовательности без повторяющихся символов до тех пор, пока не будет рассмотрен i -й индекс s1 и j-й индекс s2 . Если символы в s1[i] и s2[j] одинаковы, то dp[i][j] = dp[i-1][j-1] + 1 , иначе dp[i][j] = max(dp[ i-1][j], dp[i][j-1]) . Просто следите за повторяющимися символами, как указано в приведенном выше подходе, вместе с этим.

Примечание. В реализации массив dp реализуется с использованием карты, где ключ представляет собой конкатенированную строку i и j .

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


Временная сложность: O(N * M), где N — размер s1, а M — размер s2.
Вспомогательное пространство: O(N * M)

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