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