Максимальное количество гласных в подстроке заданного размера

Средняя

medium , string , sliding window

06 May 2024

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

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

Ограничения #

Длина строки от 1 до 100000
Строка состоит только из латинских букв в нижнем регистре
Размер подстроки находится в диапазоне от 1 до длины исходной строки s.

Примеры #

Входные данные
```
s = "abciiidef"
k = 3
```
Ответ: 3

В исходной строке есть подстрока длиной 3 состоящая исключительно из гласных iii
Входные данные
```
s = "aeiou"
k = 2
```
Ответ: 2

Исходная строк полностью состоит из гласных, поэтому любая подстрока длиной 2 будет также состоять из гласных.
Входные данные
```
s = "leetcode"
k = 3
```
Ответ: 2

В исходной строке есть несколько подстрок (lee/eet/ode), в любой из которых максимальное количество гласных равно 2.

Решение #

Данная задача является ярким представителем класса задач, которые решаются с помощью скользящего окна:

Нам необходимо создать окно длиной k (исходно левая граница окна равна 0, а правая - k-1)
Двигать наше окно увеличивая левый и правый индекс на 1 на каждом шаге
Считать сколько гласных попадает в наше окно на каждом шаге

Таким образом, исходно нам нужно посчитать сколько гласных будет в подстроке от 0 до k-1 элемента, сохранив количество как промежуточный результат. После этого мы начнем двигать наше окно. Для того чтобы каждый раз не пересчитывать заново количество гласных, нам достаточно смотреть только на изменение подстроки:

Если новый правый элемент окна является гласной — значит количество гласных относительно предыдущего окна нужно увеличить на один, так как мы включили в новой подстроке дополнительную гласную букву.
Если старый левый элемент окна является гласной — значит количество гласных относительно предыдущего окна нужно уменьшить на один, так как мы исключили из подстроки гласную букву.

Для ускорения работы стоит не забывать о раннем выходе — если на каком-то шаге мы нашли подстроку длиной k из гласных, значит нам не нужно дальше анализировать всю строку до конца.

package main

func maxVowels(s string, k int) int {
	vowelsCount := 0

	for rightIdx := 0; rightIdx < len(s) && rightIdx < k; rightIdx++ {
		if isVowel(s[rightIdx]) {
			vowelsCount++
		}
	}

	if vowelsCount == k {
		return vowelsCount
	}

	currentVowelsCount := vowelsCount
	leftIdx := 0

	for rightIdx := k; rightIdx < len(s); rightIdx++ {
		if isVowel(s[rightIdx]) {
			currentVowelsCount++
		}
		if isVowel(s[leftIdx]) {
			currentVowelsCount--
		}

		leftIdx++
		if currentVowelsCount > vowelsCount {
			vowelsCount = currentVowelsCount
			if vowelsCount == k {
				return vowelsCount
			}
		}
	}

	return vowelsCount
}

func isVowel(ch byte) bool {
	switch ch {
	case 'a':
		return true
	case 'e':
		return true
	case 'i':
		return true
	case 'o':
		return true
	case 'u':
		return true
	}
	return false
}

const isVowel = (char: string): boolean => {
    switch (char) {
        case 'a':
            return true
        case 'e':
            return true
        case 'i':
            return true
        case 'o':
            return true
        case 'u':
            return true
    }
    return false
}

export const maxVowels = (s: string, k: number): number => {
    let vowelsCount = 0

    for (let rightIdx = 0; rightIdx < s.length && rightIdx < k; rightIdx++) {
        if (isVowel(s[rightIdx])) {
            vowelsCount++
        }
    }

    if (vowelsCount == k) {
        return vowelsCount
    }

    let currentVowelsCount = vowelsCount
    let leftIdx = 0

    for (let rightIdx = k; rightIdx < s.length; rightIdx++) {
        if (isVowel(s[rightIdx])) {
            currentVowelsCount++
        }
        if (isVowel(s[leftIdx])) {
            currentVowelsCount--
        }

        leftIdx++
        if (currentVowelsCount > vowelsCount) {
            vowelsCount = currentVowelsCount
            if (vowelsCount == k) {
                return vowelsCount
            }
        }
    }

    return vowelsCount
}

Оценка сложности #

n - количество элементов в строке.

По времени

Сложность по времени O(n), так как мы гарантированно найдем ответ, перебрав полностью всю строку один раз.

По памяти

Сложность по памяти O(1).

Оригинал задачи на Leetcode

Algorithmics