max_length_of_same_char.md

Поиск длины наибольшей подстроки, в которой все буквы одинаковы

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

Условие

Задана строка S из малых латинских букв, требуется узнать длину наибольшей подстроки, в которой все буквы одинаковы.

Примеры

"" -> 0
"a" -> 1
"abbc" -> 2
"adddaabaa" -> 3
"aaaa" -> 4

Решение

    public static int maxLen(String line) {
        if (line.isEmpty()) {
            return 0;
        }

        if (line.length() == 1) {
            return 1;
        }

        int max = 0;
        int currentMax = 0;
        char elem = line.charAt(0);

        for (char e : line.toCharArray()) {
            if (elem == e) {
                currentMax++;
            } else {
                if (currentMax > max) {
                    max = currentMax;
                }

                currentMax = 1;
                elem = e;
            }
        }

        // если все в строке элементы одни и те же
        if (currentMax > max) {
            max = currentMax;
        }

        return max;
    }

Необходимо идти по строке, отслеживая тот момент, когда символ будет изменен. Пока мы идем по подстроке с одинаковыми символами наращиваем локальный максимум.

При смене символа локальный максимум сверяется с тем, что будет ответом.

Главное не забыть краевые случаи: когда вся последовательность состоит из одних символов, пустая строка, когда происходит смена символа и что было до этого.

Время работы: O(N)

Память: O(1)