Skip to content

3641. Longest Semi-Repeating Subarray πŸ”’

Description

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.

 

Example 1:

Input: nums = [1,2,3,1,2,3,4], k = 2

Output: 6

Explanation:

The longest semi-repeating subarray is [2, 3, 1, 2, 3, 4], which has two repeating elements (2 and 3).

Example 2:

Input: nums = [1,1,1,1,1], k = 4

Output: 5

Explanation:

The longest semi-repeating subarray is [1, 1, 1, 1, 1], which has only one repeating element (1).

Example 3:

Input: nums = [1,1,1,1,1], k = 0

Output: 1

Explanation:

The longest semi-repeating subarray is [1], which has no repeating elements.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 0 <= k <= nums.length

Solutions

Solution 1: Sliding Window

Thinking

A window is semi-repeating when the number of values that occur at least twice is at most \(k\). Longer windows are stricter, so the left end only moves right as the right end advances.

A frequency map updates a counter of repeated values: increment when a count rises from \(1\) to \(2\), decrement when it falls from \(2\) to \(1\). Shrink the left side while that counter exceeds \(k\).

Each index enters and leaves once; the answer is the longest legal window.

We use two pointers \(l\) and \(r\) to maintain a sliding window, where the right pointer continuously moves to the right, and we use a hash table \(\textit{cnt}\) to record the number of occurrences of each element within the current window.

When the occurrence count of an element changes from \(1\) to \(2\), it indicates that there is a new repeating element, so we increment the repeating element counter \(\textit{cur}\) by \(1\). When the repeating element counter exceeds \(k\), it means the current window does not satisfy the condition, and we need to move the left pointer until the repeating element counter is no greater than \(k\). During the process of moving the left pointer, if the occurrence count of an element changes from \(2\) to \(1\), it indicates that there is one less repeating element, so we decrement the repeating element counter by \(1\). Then, we update the answer, i.e., \(\textit{ans} = \max(\textit{ans}, r - l + 1)\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestSubarray(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        ans = cur = l = 0
        for r, x in enumerate(nums):
            cnt[x] += 1
            cur += cnt[x] == 2
            while cur > k:
                cnt[nums[l]] -= 1
                cur -= cnt[nums[l]] == 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestSubarray(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0, cur = 0, l = 0;
        for (int r = 0; r < nums.length; ++r) {
            if (cnt.merge(nums[r], 1, Integer::sum) == 2) {
                ++cur;
            }
            while (cur > k) {
                if (cnt.merge(nums[l++], -1, Integer::sum) == 1) {
                    --cur;
                }
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestSubarray(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int ans = 0, cur = 0, l = 0;
        for (int r = 0; r < nums.size(); ++r) {
            if (++cnt[nums[r]] == 2) {
                ++cur;
            }
            while (cur > k) {
                if (--cnt[nums[l++]] == 1) {
                    --cur;
                }
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func longestSubarray(nums []int, k int) (ans int) {
    cnt := make(map[int]int)
    cur, l := 0, 0
    for r := 0; r < len(nums); r++ {
        if cnt[nums[r]]++; cnt[nums[r]] == 2 {
            cur++
        }
        for cur > k {
            if cnt[nums[l]]--; cnt[nums[l]] == 1 {
                cur--
            }
            l++
        }
        ans = max(ans, r-l+1)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function longestSubarray(nums: number[], k: number): number {
    const cnt: Map<number, number> = new Map();
    let [ans, cur, l] = [0, 0, 0];
    for (let r = 0; r < nums.length; r++) {
        cnt.set(nums[r], (cnt.get(nums[r]) || 0) + 1);
        if (cnt.get(nums[r]) === 2) {
            cur++;
        }

        while (cur > k) {
            cnt.set(nums[l], cnt.get(nums[l])! - 1);
            if (cnt.get(nums[l]) === 1) {
                cur--;
            }
            l++;
        }

        ans = Math.max(ans, r - l + 1);
    }

    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
use std::collections::HashMap;

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
        let mut cnt = HashMap::new();
        let mut ans = 0;
        let mut cur = 0;
        let mut l = 0;

        for r in 0..nums.len() {
            let entry = cnt.entry(nums[r]).or_insert(0);
            *entry += 1;
            if *entry == 2 {
                cur += 1;
            }

            while cur > k {
                let entry = cnt.entry(nums[l]).or_insert(0);
                *entry -= 1;
                if *entry == 1 {
                    cur -= 1;
                }
                l += 1;
            }

            ans = ans.max(r - l + 1);
        }

        ans as i32
    }
}

Comments