Жадная сборка строки с ограничениями 😊

leetcoder, 17-12-2024 ,

109

Сегодня нам предстоит несложная задача - 2182. Construct String With Repeat Limit. Но технически она получилась муторной - требует от программиста очень аккуратного подхода к себе :)

Задача 📜

Дана строка s, состоящая из произвольных символов, и число repeat_limit. Необходимо построить лексикографически максимальную строку, используя символы из s, но с ограничением:

один и тот же символ не может встречаться более repeat_limit раз подряд.

Подход 🚀

Подсчёт частоты символов:
- Используем массив размера 256, чтобы подсчитать количество вхождений каждого байта (символа).
Жадный выбор символов:
- Обходим пространство символов (0–255), начиная с самого большого.
- Добавляем текущий символ в результат до repeat_limit раз или пока его количество не исчерпается.
- Если нужно "разорвать" последовательность, вставляем следующий по величине символ, уменьшая его количество.
Эффективный поиск следующего символа:
- Вспомогательная функция find_last_valid_index ищет ближайший допустимый символ с ненулевой частотой, используя знание о текущем символе как ускоряющую подсказку.

Асимптотика 📊

Вычислительная сложность

Подсчёт частот: O(N), где N — длина строки s.
Обход пространства байтов (0–255):
- Хотя мы потенциально сканируем до 256 символов с возможными повторениями, каждая итерация либо добавляет символ в результат, либо завершает выполнение.
- Ключевое наблюдение: Каждый символ из исходной строки добавляется в результат не более одного раза, что обеспечивает общее время работы O(N).
Всего: O(N)

Пространственная сложность

O(1): используем фиксированного размера массив для подсчёта частот символов.

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

impl Solution {
    pub fn repeat_limited_string(s: String, repeat_limit: i32) -> String {
        let mut count = [0; 256]; // Count occurrences of each byte (0-255)

        // Step 1: Count occurrences of each character
        for &b in s.as_bytes() {
            count[b as usize] += 1;
        }

        let mut result = String::new();
        let mut current_index = Self::find_last_valid_index(&count, 255);

        while let Some(idx) = current_index {

            // Find the next largest valid byte smaller than `current_index`
            let next_index = Self::find_last_valid_index(&count, idx - 1);

            // Append `repeat_limit` or fewer occurrences of the current byte
            let use_count = repeat_limit.min(count[idx]);
            for _ in 0..use_count {
                result.push(idx as u8 as char);
            }
            count[idx] -= use_count;

            // If there are still occurrences left, insert one byte of `next_index`
            if count[idx] > 0 {
                if let Some(next_idx) = next_index {
                    result.push(next_idx as u8 as char);
                    count[next_idx] -= 1;
                } else {
                    break; // No valid character to break the sequence
                }
            } else {
                current_index = next_index;
            }
        }

        result
    }

    // Helper function to find the last valid index with non-zero count
    fn find_last_valid_index(count: &[i32], mut index: usize) -> Option<usize> {
        while index > 0 {
            if count[index] > 0 {
                return Some(index);
            }
            index -= 1;
        }
        None // Return None if no valid index is found
    }
}