0

Можете, пожалуйста, объяснить, что такое границы подстроки. Вот просто есть задача: https://leetcode.com/problems/longest-substring-without-repeating-characters/ и я видел, как кто-то писал, что в качестве наивного алгоритма можно использовать "перебирание границ подстроки" за О(n^2), а потом сравнивать каждый символ с каждым за О(n^2). Но я вообще не понял, что такое "перебирание границ подстроки" и почему оно выполняется за O(n^2)? Заранее спасибо!

1 ответ 1

4

Подстрока однозначно задается парой неотрицательных чисел меньших длины исходной строки (возможно одинаковых, но таких что первое не больше второго). Более того, любой такой паре соответствует одна подстрока. (Т.к. эта пара задает номера в исходной строке первого и последнего символа образующих подстроку.) Вот эта пара и есть границы подстроки. Всего таких пар n*(n+1)/2, т.е. O(n^2). (Это я пустую подстроку игнорю.)

2
  • а можно какой-то пример, чтобы убедиться? 15 сен 2021 в 23:36
  • @randomuser228 , ну вот есть строка abc. n=3. Пары -- (0,0);(0,1);(0,2);(1,1);(1,2);(2,2). Им соответствуют подстроки a,ab,abc,b,bc,c. 6 как раз, по формуле. "Перебрать границы подстроки" -- значит перебрать все эти пары.
    – user457226
    15 сен 2021 в 23:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.