Как алгоритмически найти индекс начала второй по длине последовательности нулей и её длину в строке из 0 и 1

Что проверяют

Умеете ли вы решить задачу за один проход без лишней памяти и аккуратно обработать края: серию в конце строки, равные длины, отсутствие второй серии. Следом спрашивают сложность и просят прогнать решение на своих примерах.

Как отвечать

Начните с уточнения условия, это половина оценки. Что считать второй по длине, если две самые длинные серии равны: вторую из них или следующую строго короче? Что вернуть, если серия одна или нулей нет? Проверять ли, что в строке только 0 и 1?

Решение за O(n) по времени и O(1) по памяти, без списков и сортировки:

• текущая серия: идём по s.charAt(i), на первом нуле серии запоминаем start, на каждом следующем увеличиваем len;
• закрытие серии: на единице сравниваем серию с двумя лучшими. Если len > bestLen, лучшая сдвигается во вторую, текущая становится лучшей. Иначе, если len > secondLen, текущая становится второй;
• хвост: серия, дошедшая до конца строки, закрывается после цикла. Удобный приём: крутить цикл до i <= n и считать позицию n единицей, тогда ветка закрытия одна;
• результат: record с полями start и len, либо -1 и 0, если второй серии нет.

Строгое > означает, что при равных длинах выигрывает более ранняя серия. Если нужна строго более короткая, во второе условие добавляется len < bestLen.

Прогоните вслух. В 100001000010000 три серии по четыре нуля с началом в 1, 6 и 11. Если равные длины считаются, ответ: индекс 6, длина 4. Для 00011000 ответ: индекс 5, длина 3. Для 111 второй серии нет.

Где спотыкаются

Забывают серию в конце строки. Решение проходит примеры, которые кончаются единицей, и ломается на 1001000: последняя серия из трёх нулей теряется, и программа говорит, что второй серии нет.

Собирают все серии в список и сортируют. Это O(k log k) и лишняя память, а интервьюер почти наверняка спросит, можно ли за один проход.

Не уточняют правило для равных длин и молча выбирают одно из толкований. Если интервьюер имел в виду другое, решение сочтут неверным, хотя код рабочий.