Подсчет символов строки, удаление которых по отдельности делает строку равной другой строке

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

Имея две строки A и B размера N и M соответственно, задача состоит в том, чтобы подсчитать символы строки A , которые при удалении по отдельности делают обе строки равными. Если таких символов несколько, то выведите их соответствующие позиции. В противном случае выведите «-1» .

Примеры:

Input: A = “abaac”, B = “abac”
Output: 2
             3 4
Explanation: 
Following removals are possible that can make the strings equal:

  1. Removing A[2] modifies A to “abac”, which becomes equal to B.
  2. Removing A[3] modifies A to “abac”, which becomes equal to B.

Therefore, two possible removals satisfy the conditions.

Input: A = “abs”, B = “bkk”
Output: -1

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  • Suppose, if removing the character at index i, makes both strings equal then the prefix of the string i.e substring over the range [0, i-1] must be equal and the suffix of the string i.e substring over the range [i+1, N-1] must be equal too.
  • Suppose i is the index satisfying that the substring over the range [0, i-1] is the longest equal prefix string. And j is the index satisfying that the substring over the range [j+1, N-1] is the longest equal suffix string
  • Then, if i>=j then only, there exist characters removing which makes the both strings equal. And total count of such characters removing which individually makes the strings equal is i-j+1.

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

  • Инициализируйте две переменные, скажем, X как 0 и Y как N-1 , чтобы сохранить конечный индекс самой длинной строки равного префикса и начальный индекс самой длинной строки равного суффикса.
  • Перебрать символы строки B , а затем на каждой итерации проверить, равен ли текущий символ символу с индексом X строки A , а затем увеличить X на 1 . В противном случае сломайтесь.
  • Перебрать символы строки B в обратном порядке, а затем на каждой итерации проверить, равен ли текущий символ символу с индексом Y строки A , а затем уменьшить Y на 1 . В противном случае сломайтесь.
  • Теперь, если разница между N и M равна 1 , а Y меньше X , тогда:
    • Выведите общее количество таких символов в виде X-Y+1.
    • Затем напечатайте индексы символа, перебирая диапазон [Y+1, X+1].
  • В противном случае выведите «-1».

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

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

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