rust_algorithms/other/

sliding_window.rs

//! Siljuvchi oyna (sliding window) texnikasi.
//!
//! **G'oya:** ketma-ket elementlardan iborat "oyna" bo'ylab yuramiz. Oynani
//! har safar noldan hisoblash o'rniga, **chiqib ketganini ayirib, kirganini qo'shamiz**.
//!
//! ```text
//!  [1, 4, 2, 10, 2, 3, 1, 0, 20]   k = 4
//!   └────oyna────┘                 yig'indi = 17
//!      └────oyna────┘              yig'indi = 17 − 1 + 2 = 18
//! ```
//!
//! Natijada O(n·k) o'rniga **O(n)**.
//!
//! Ikki turi bor:
//! - **Qat'iy o'lchamli** oyna ([`max_sum_subarray_k`]);
//! - **O'zgaruvchan** o'lchamli oyna ([`longest_unique_substring`], [`min_subarray_len`]).

use std::collections::HashMap;

/// `k` uzunlikdagi qism-massivning maksimal yig'indisi.
///
/// - **Time:** O(n), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::other::sliding_window::max_sum_subarray_k;
///
/// assert_eq!(max_sum_subarray_k(&[1, 4, 2, 10, 2, 3, 1, 0, 20], 4), Some(24));
/// assert_eq!(max_sum_subarray_k(&[1, 2], 5), None); // k massivdan katta
/// ```
pub fn max_sum_subarray_k(nums: &[i64], k: usize) -> Option<i64> {
    if k == 0 || k > nums.len() {
        return None;
    }
    let mut yigindi: i64 = nums[..k].iter().sum();
    let mut eng_katta = yigindi;

    for i in k..nums.len() {
        yigindi += nums[i] - nums[i - k]; // kirdi − chiqdi
        eng_katta = eng_katta.max(yigindi);
    }
    Some(eng_katta)
}

/// Takrorlanuvchi belgisiz eng uzun qism-satr uzunligi.
///
/// **G'oya (o'zgaruvchan oyna):** o'ng chetni surib boramiz; takror belgi uchrasa,
/// chap chetni o'sha belgining oldingi joyidan keyingi pozitsiyaga "sakratamiz".
///
/// - **Time:** O(n), **Space:** O(alifbo hajmi).
///
/// # Misol
/// ```
/// use rust_algorithms::other::sliding_window::longest_unique_substring;
///
/// assert_eq!(longest_unique_substring("abcabcbb"), 3); // "abc"
/// assert_eq!(longest_unique_substring("bbbbb"), 1);    // "b"
/// assert_eq!(longest_unique_substring("pwwkew"), 3);   // "wke"
/// assert_eq!(longest_unique_substring(""), 0);
/// ```
pub fn longest_unique_substring(s: &str) -> usize {
    let belgilar: Vec<char> = s.chars().collect();
    let mut oxirgi_orin: HashMap<char, usize> = HashMap::new();
    let mut chap = 0usize;
    let mut eng_uzun = 0usize;

    for (ong, &ch) in belgilar.iter().enumerate() {
        if let Some(&orin) = oxirgi_orin.get(&ch) {
            if orin >= chap {
                chap = orin + 1; // oynani takrordan keyinga surib yuboramiz
            }
        }
        oxirgi_orin.insert(ch, ong);
        eng_uzun = eng_uzun.max(ong - chap + 1);
    }
    eng_uzun
}

/// Yig'indisi `target` dan **kam bo'lmagan** eng qisqa qism-massiv uzunligi.
///
/// Musbat sonlar uchun. Topilmasa — `None`.
///
/// - **Time:** O(n), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::other::sliding_window::min_subarray_len;
///
/// assert_eq!(min_subarray_len(&[2, 3, 1, 2, 4, 3], 7), Some(2)); // [4, 3]
/// assert_eq!(min_subarray_len(&[1, 1, 1], 10), None);
/// ```
pub fn min_subarray_len(nums: &[i64], target: i64) -> Option<usize> {
    let mut chap = 0usize;
    let mut yigindi = 0i64;
    let mut eng_qisqa = usize::MAX;

    for ong in 0..nums.len() {
        yigindi += nums[ong];
        while yigindi >= target {
            eng_qisqa = eng_qisqa.min(ong - chap + 1);
            yigindi -= nums[chap];
            chap += 1;
        }
    }
    if eng_qisqa == usize::MAX {
        None
    } else {
        Some(eng_qisqa)
    }
}

/// Har bir `k` o'lchamli oynadagi maksimal element (monoton deque bilan).
///
/// **G'oya:** deque ichida indekslarni **qiymatlari kamayadigan** tartibda saqlaymiz.
/// Boshidagi indeks — joriy oynaning maksimumi. Har bir element deque ga
/// bir marta kiradi va bir marta chiqadi → **O(n)**.
///
/// # Misol
/// ```
/// use rust_algorithms::other::sliding_window::max_in_windows;
///
/// assert_eq!(
///     max_in_windows(&[1, 3, -1, -3, 5, 3, 6, 7], 3),
///     vec![3, 3, 5, 5, 6, 7]
/// );
/// ```
pub fn max_in_windows(nums: &[i64], k: usize) -> Vec<i64> {
    use std::collections::VecDeque;

    if k == 0 || k > nums.len() {
        return Vec::new();
    }
    let mut deque: VecDeque<usize> = VecDeque::new();
    let mut natija = Vec::with_capacity(nums.len() - k + 1);

    for i in 0..nums.len() {
        // oynadan chiqib ketgan indeksni olib tashlaymiz
        if let Some(&bosh) = deque.front() {
            if bosh + k <= i {
                deque.pop_front();
            }
        }
        // yangi elementdan kichik bo'lganlar hech qachon maksimum bo'lolmaydi
        while let Some(&oxir) = deque.back() {
            if nums[oxir] <= nums[i] {
                deque.pop_back();
            } else {
                break;
            }
        }
        deque.push_back(i);

        if i + 1 >= k {
            natija.push(nums[*deque.front().unwrap()]);
        }
    }
    natija
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::util::Rng;

    #[test]
    fn oyna_yigindisi_bruteforce_bilan_mos() {
        let mut rng = Rng::new(1101);
        for _ in 0..30 {
            let v = rng.vec(50, -20, 20);
            for k in 1..=10 {
                let kutilgan = v.windows(k).map(|w| w.iter().sum::<i64>()).max();
                assert_eq!(max_sum_subarray_k(&v, k), kutilgan, "k = {k}");
            }
        }
    }

    #[test]
    fn takrorsiz_qism_satr() {
        assert_eq!(longest_unique_substring("abcdef"), 6);
        assert_eq!(longest_unique_substring("aab"), 2);
        assert_eq!(longest_unique_substring("dvdf"), 3);
        assert_eq!(longest_unique_substring("o'zbek"), 6);
    }

    #[test]
    fn eng_qisqa_qism_massiv() {
        assert_eq!(min_subarray_len(&[1, 4, 4], 4), Some(1));
        assert_eq!(min_subarray_len(&[], 1), None);
        assert_eq!(min_subarray_len(&[1, 2, 3, 4, 5], 15), Some(5));
    }

    #[test]
    fn oynadagi_maksimum_bruteforce_bilan_mos() {
        let mut rng = Rng::new(1102);
        for _ in 0..30 {
            let v = rng.vec(60, -50, 50);
            for k in 1..=8 {
                let kutilgan: Vec<i64> = v.windows(k).map(|w| *w.iter().max().unwrap()).collect();
                assert_eq!(max_in_windows(&v, k), kutilgan, "k = {k}");
            }
        }
        assert!(max_in_windows(&[1, 2], 5).is_empty());
    }
}