Ссылка на задачу — 3306. Count of Substrings Containing Every Vowel and K Consonants II.
📌 Условие задачи
Дана строка word
и неотрицательное число k
.
Необходимо подсчитать количество подстрок, в которых встречаются все гласные буквы ('a', 'e', 'i', 'o', 'u'
) хотя бы по одному разу и ровно k
согласных.
💡 Идея
Будем использовать подход «скользящего окна», отслеживая позиции последних появлений гласных и согласных букв.
Это позволяет эффективно перемещать границы окна и быстро проверять условия задачи при изменении количества согласных и наличии всех гласных.
🛠️ Детали подхода
- Для каждой гласной буквы сохраняется её последняя позиция.
- Для согласных используется итератор, последовательно предоставляющий позиции согласных в строке.
- Если количество согласных становится больше
k
, левая граница окна перемещается вперёд.
- При каждом совпадении условий (ровно
k
согласных и присутствуют все гласные) подсчитывается количество допустимых подстрок.
⏳ Асимптотика
- Время:
O(n)
– каждый символ строки обрабатывается не более двух раз.
- Память:
O(1)
– используются только дополнительные константные структуры данных для отслеживания позиций.
📦 Исходный код
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