Самая длинная подстрока, любая непустая подстрока которой не является префиксом или суффиксом данной строки

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

Для заданной строки S длины N задача состоит в том, чтобы найти длину самой длинной подстроки X строки S , такой что:

  • Никакая непустая подстрока X не является префиксом S.
  • Никакая непустая подстрока X не является суффиксом S.
  • Если такая строка невозможна, выведите −1.

Примеры:

Input: S = “abcdefb”
Output: 4
Explanation: cdef is the substring satisfying the conditions.

Input: S = “cccc”
Output: -1
Explanation: No substring can satisfy the conditions.

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

Наблюдения:

Since a prefix starts from a starting of string S and a suffix starts from ending of a string S. Therefore maximum length of substring can be length of string S – 2 and it cannot have elements which are at the starting or ending of the string.
So select the substring not having any character which is the first or last character of the string. this will the largest substring satisfying the conditions.

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

  • Пройдите по строке от i = 1 до конца строки .
    • Проверьте, не найден ли какой-либо символ, который не равен первому и последнему символу строки.
    • Если найдено, считайте его частью результирующей подстроки.
    • В противном случае он не будет включен в подстроку.
  • Результатом будет максимальная длина подстроки, удовлетворяющей условиям.

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

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

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