Найти в строке подстроку, которая содержит максимальное количество последовательных символов в этой строке?

Question

[amatoriste]

К примеру.
Есть строка

$str= 'abcccdefghijklm234nnnnopqqrerrstuvwxyz0156789';

Нужно получить из неё подстроку, с максимальным количеством последовательных символов .

Есть идея:
сделать через preg_split() , найти уникальные подстроки и потом пройти по массиву и найти строку с макс. длинной.
Но я застопорился с самой регуляркой.
Не могу раздуплиться как правильно записать последовательность без повторений.
Может есть Добрый Человек который может подсказать?))

Comments

[Сергей Соколов]

«последовательных» – это именно в порядке возрастания ASCII кода на 1? «abcdef» последовательна, а «acebdf» – нет?

[amatoriste]

нет, последовательных имеется виду не повторяющихся в подстроке

Answer 1

[Сергей Соколов]

Надо двигать концы отрезка: правый R и левый L. Изначально оба на нуле.
Держим текущий набор символов, чтобы проверять на повторы. Помним найденный максимальный отрезок.
Двигаем правый конец на 1. Если символа нет в наборе, добавляем. Если есть, двигаем L вправо за найденный символ. Перед этим проверяем, а не нашли ли мы очередной максимум.

Очень кривая спать-хочу реализация, вроде, работает: Ideone

Старый ответ, please ignore: Двигаться по одному символу. Помнить найденную макс. длину. Сравнивать символ с предыдущим.
Равен – длина текущего сегмента растёт.
Не равен – закончился предыдущий сегмент и начался новый. Если длина больше найденного максимума – найден очередной кандидат. Запомнить его длину и начало. Запомнить начало очередного сегмента и считать длину с 1.

Итого один раз пройтись. Не надо регулярок.

Answer 2

[xmoonlight]

Никого не слушайте: Это Хаффман.

Comments

[Сергей Соколов]

Как-то длинно написали. Можно же просто «берёте и ищете».

[xmoonlight]

Сергей Соколов: Я - поправил! ;)

Answer 3

[Immortal_pony]

function findTheLongestSequence($str) {
    $sequences = [];
    $sequence = "";
    
    for ($letterIndex=0; $letterIndex<strlen($str); $letterIndex++) {
        $letter = $str[$letterIndex];
        $previousLetterIndex = ($letterIndex-1);
        $previousLetter = (isset($str[$previousLetterIndex]) ? $str[$previousLetterIndex] : null);

        if ($previousLetter === $letter) {
            if (!empty($sequence)) {
                $sequences[] = $sequence;
                $sequence = "";
            }
        } else {
            $sequence .= $letter;
        }
        
        if (strlen($str)-1 === $letterIndex && !empty($sequence)) {
            $sequences[] = $sequence;
        }
    }
    
    usort($sequences, function($someSequence, $otherSequence) {
        return strlen($otherSequence)-strlen($someSequence);
    });
    
    return $sequences[0];
}

PS Если программист начинает решать проблему с помощью регулярного выражения, то у него появляется две проблемы(с).