Сегодня на очереди задача 2825. Make String a Subsequence Using Cyclic Increments.
Описание задачи 📝
Даны две строки str1 и str2. Нужно определить, можно ли сделать str2 подпоследовательностью строки str1, выполнив не более одной операции циклического увеличения произвольного набора символов в str1.
Циклический сдвиг означает, что 'a' становится 'b', 'b' — 'c', ..., 'z' — 'a'.
Идея решения 💡
Задача почти идентична проверке подпоследовательности в строке. Единственное отличие — сравнение символов становится чуть сложнее из-за необходимости учитывать циклический сдвиг.
Мы выделяем проверку совпадения символов в отдельный метод, а в остальном используем стандартный алгоритм проверки подпоследовательности.
Реализация подхода 🚀
- Используем два итератора для последовательного прохода по символам строк.
- Для сравнения символов применяем отдельную функцию, учитывающую как прямое совпадение, так и циклический сдвиг.
- При совпадении текущего символа строки
str2 с символом из str1, переходим к следующему символу в str2.
- Если все символы
str2 найдены в str1 в правильном порядке, возвращаем true, иначе — false.
Сложность алгоритма 📊
- Временная сложность:
O(n+m), где n — длина str1, m — длина str2.
- Каждая строка обрабатывается ровно один раз.
- Пространственная сложность:
O(1).
- Используются только итераторы без дополнительных структур данных.
Исходный код решения
impl Solution {
pub fn can_make_subsequence(str1: String, str2: String) -> bool {
// Helper function to check if characters match with cyclic increment
fn is_match(c1: char, c2: char) -> bool {
c1 == c2 || (c1 as u8 + 27 - c2 as u8) % 26 == 0
}
let mut s2 = str2.chars();
let mut it2 = s2.next();
for c1 in str1.chars() {
if let Some(c2) = it2 {
if is_match(c1, c2) {
it2 = s2.next(); // Move to the next character in str2
}
} else {
break; // All characters in str2 are matched
}
}
// If we have exhausted all characters in str2, return true
it2.is_none()
}
}