Longest semi repeating subarray

Array Hash Table Sliding Window

64.4% acceptance

Mar 31, 2026

You are given an integer array nums of length n and an integer k. A semi‑repeating subarray is a contiguous subarray in which at most k elements repeat (i.e., appear more than once). Return the length of the longest semi‑repeating subarray in nums.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
    use std::collections::HashMap;
    let n = nums.len();
    let mut freq: HashMap<i32, i32> = HashMap::new();
    let mut repeating = 0i32; // count of elements with freq > 1
    let mut left = 0;
    let mut ans = 0;

    for right in 0..n {
      let f = freq.entry(nums[right]).or_insert(0);
      *f += 1;
      if *f == 2 {
        repeating += 1;
      }

      while repeating > k {
        let fl = freq.get_mut(&nums[left]).unwrap();
        *fl -= 1;
        if *fl == 1 {
          repeating -= 1;
        }
        left += 1;
      }

      ans = ans.max(right - left + 1);
    }

    ans as i32
  }
}