главная новое лучшее написать
3

Ссылка на задачу — 3306. Count of Substrings Containing Every Vowel and K Consonants II.

📌 Условие задачи

Дана строка word и неотрицательное число k.
Необходимо подсчитать количество подстрок, в которых встречаются все гласные буквы ('a', 'e', 'i', 'o', 'u') хотя бы по одному разу и ровно k согласных.

💡 Идея

Будем использовать подход «скользящего окна», отслеживая позиции последних появлений гласных и согласных букв.
Это позволяет эффективно перемещать границы окна и быстро проверять условия задачи при изменении количества согласных и наличии всех гласных.

🛠️ Детали подхода

  1. Для каждой гласной буквы сохраняется её последняя позиция.
  2. Для согласных используется итератор, последовательно предоставляющий позиции согласных в строке.
  3. Если количество согласных становится больше k, левая граница окна перемещается вперёд.
  4. При каждом совпадении условий (ровно k согласных и присутствуют все гласные) подсчитывается количество допустимых подстрок.

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

📦 Исходный код

impl Solution {
    const CONSONANT_INDEX: usize = 5;

    pub fn count_of_substrings(word: String, k: i32) -> i64 {
        let word_bytes = word.as_bytes();

        // Iterators 
        // 1: vowel_idx_enumerator - over all characters mapped to the simple vowel index 
        //      'a' → 0, 'e' → 1, 'i' → 2, 'o' → 3, 'u' → 4, consonant → 5
        // 2: cons_pos_iter - over consonant positions, infinitely padded with word length
        let mut vowel_idx_enumerator = word_bytes.iter().map(Self::char_index).enumerate();
        let mut cons_pos_iter = vowel_idx_enumerator.clone()
            .filter_map(|(pos, idx)| if idx == Self::CONSONANT_INDEX { Some(pos) } else { None })
            .chain(std::iter::repeat(word_bytes.len()))
            .peekable();

        let mut last_vowel_pos = [None; 5]; // Tracks latest positions for vowels
        let mut left_cons = 0;
        let mut consonant_count = 0;
        let mut total = 0i64;

        for (right, vowel_idx) in vowel_idx_enumerator {
            if vowel_idx < Self::CONSONANT_INDEX {
                // Update latest vowel position
                last_vowel_pos[vowel_idx] = Some(right);
            } else {
                consonant_count += 1;

                // Move consonant window forward when exceeding k consonants
                if consonant_count > k {
                    consonant_count -= 1;
                    left_cons = cons_pos_iter.next().expect("Infinite iterator ended") + 1;
                }
            }

            // If exactly k consonants, count valid substrings
            if consonant_count == k {
                let earliest_required_pos = last_vowel_pos.iter()
                    .chain(std::iter::once(&cons_pos_iter.peek().copied()))
                    .min()
                    .expect("Iterator should never be empty")
                    .map_or(0, |m| m + 1);

                total += (earliest_required_pos.saturating_sub(left_cons)) as i64;
            }
        }

        total
    }

    #[inline]
    fn char_index(ch: &u8) -> usize {
        match ch {
            b'a' => 0,
            b'e' => 1,
            b'i' => 2,
            b'o' => 3,
            b'u' => 4,
            _ => Self::CONSONANT_INDEX,
        }
    }
}

Tags: #rust #algorithms