Строку набирают в редакторе двумя операциями:
- напечатать символ — дописать один символ в конец;
- копировать-вставить — скопировать любой уже напечатанный непрерывный
фрагмент и вставить его в конец.
Каждая операция стоит единицу. Посимвольный набор строки длины n стоит n
операций. Нужно определить, можно ли набрать строку строго быстрее, чем за
n операций.
// CanTypeFaster сообщает, можно ли набрать s менее чем за len([]rune(s)) операций.
func CanTypeFaster(s string) bool
Примеры
"wxyz" → false // все символы разные, копировать нечего
"wxyzwx" → true // напечатать w,x,y,z, затем вставить "wx" — 5 операций вместо 6
"aaa" → false // "aa" можно вставить, но получится 4 символа; за 3 операции только печать
"aaaa" → true // напечатать "aa", вставить "aa" — 3 операции вместо 4
Пояснение
На каждом шаге уже набранный текст — это некоторый префикс s. Вставка
копирует непрерывный фрагмент этого префикса и дописывает его в конец, поэтому
вставленный фрагмент обязан совпасть с нужным куском s. Выгода появляется
только от вставки длины ≥ 2 (вставка одного символа стоит столько же, сколько
печать).
Ограничения
s — строка из Unicode-символов, возможно пустая, работай по рунам.- Ожидается не хуже O(n) по времени (хватает одного прохода).
Устно: а как посчитать минимальное число операций, а не только факт
«можно быстрее»?