🏆 Оптимальный анализ подстрок, состоящих из одного символа

leetcoder, 10-12-2024 ,

249

На этот раз наша задача выглядит заковыристо - 2982. Find Longest Special Substring That Occurs Thrice II.

📝 Описание задачи

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

"Особенная" подстрока — это подстрока, содержащая один и тот же символ.

😊 Идея

Отбросим сразу идею перебора всех возможных подстрок (что крайне неэффективно).
Вместо этого мы сосредоточимся на последовательных участках каждого символа.
Для каждого символа достаточно рассмотреть только длины его подряд идущих сегментов, и это позволит нам эффективно вычислить искомый результат.

🚀 Подход

Перебираем все строчные английские буквы ('a' до 'z').
Для каждой буквы:
- Находим все её подряд идущие сегменты (например, для 'aaaabbaab' сегменты: [4,2], [2,1] для 'a' и 'b').
- Сортируем длины сегментов по убыванию.
- Вычисляем максимальную возможную длину "особенной" подстроки, встречающейся как минимум три раза, используя метод get_triple_length.
Поддерживаем глобальный максимум для всех символов.
Если не найдено ни одной подходящей подстроки, возвращаем -1.

⏱ Сложность по времени

Поиск сегментов: O(n) на один символ.
Сортировка сегментов: O(klog⁡k), где k — количество сегментов для текущего символа.
Итоговая сложность: O(26×(n+klog⁡k)), но на практике O(n), так как k≪n.

🗂 Сложность по памяти

Сегменты: O(k) для текущего символа.
Общая сложность: O(k), что на практике значительно меньше длины строки.

Исходный код решения

impl Solution {
    pub fn maximum_length(s: String) -> i32 {
        let mut best = -1;
        let data = s.as_bytes();

        // Iterate over all lowercase English letters
        for ch in b'a'..=b'z' {
            let segments = Solution::get_segments(data, ch);
            if !segments.is_empty() {
                best = best.max(Solution::get_triple_length(&segments));
            }
        }
        best
    }

    // Function to calculate the maximum length of a segment that occurs at least three times.
    fn get_triple_length(segments: &Vec<usize>) -> i32 {
        let mut max_length = (segments[0] as i32) - 2;
        if segments.len() > 1 && segments[1] >= (max_length + 1) as usize {
            max_length += 1;
            if segments.len() > 2 && segments[2] >= (max_length + 1) as usize {
                max_length += 1;
            }
        }

        if max_length > 0 {
            max_length
        } else {
            -1
        }
    }

    // Function to find lengths of consecutive characters in the string for a given character.
    fn get_segments(data: &[u8], ch: u8) -> Vec<usize> {
        let mut segments = Vec::new();
        let mut i = 0;

        while i < data.len() {
            if data[i] == ch {
                let mut length = 1;
                // Count consecutive characters matching `ch`
                while i + length < data.len() && data[i + length] == ch {
                    length += 1;
                }
                segments.push(length);
                i += length; // Skip the rest of the segment
            }
            i += 1;
        }

        // Sort segments in descending order
        segments.sort_by(|a, b| b.cmp(a));
        segments
    }
}