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 <= 10⁵
1 <= nums[i] <= 10⁵
0 <= k <= nums.length

FOR TESTING ONLY. WILL BE DELETED LATER.

// Model solution has runtime of O(n log n), O(n*n) and above should TLE.

# Bromelia

import sys
import random, json, string
import math
import datetime
from collections import defaultdict
ri = random.randint

MAX_N   = 100_000
MAX_VAL = 100_000

def randomString(n, allowed):
    return ''.join(random.choices(allowed, k=n))

def randomUnique(x, y, n):
    return random.sample(range(x, y + 1), n)

def randomArray(x, y, n):
    return [ri(x, y) for _ in range(n)]

def shuffle(arr):
    random.shuffle(arr)
    return arr

def pr(a):
    file.write(str(a).replace(" ", "").replace("\'", "\"").replace("\"null\"", "null") + '\n')

def prstr(a):
    pr("\"" + a + "\"")


def prtc(tc):
    nums, k = tc
    pr(nums)
    pr(k)

def examples():
    yield ([1, 2, 3, 1, 2, 3, 4], 2)
    yield ([1, 1, 1, 1, 1], 4)
    yield ([1, 1, 1, 1, 1], 0)

def smallCases():
    yield ([MAX_VAL], 0)
    yield ([MAX_VAL], 1)

    for len in range(1, 3 + 1):
        nums = [0] * len

        def recursiveGenerate(idx: int):
            if idx == len:
                for k in range(0, len + 1):
                    yield (nums, k)
            else:
                for nextElement in range(1, len + 1):
                    nums[idx] = nextElement
                    yield from recursiveGenerate(idx + 1)

        yield from recursiveGenerate(0)

def randomCases():
    params = [
        (    4,    20,      10, 400),
        (   21,  2000,    1000, 100),
        (MAX_N, MAX_N,      10,   2),
        (MAX_N, MAX_N,     500,   2),
        (MAX_N, MAX_N, MAX_VAL,   2),
    ]
    for minLen, maxLen, maxVal, testCount in params:
        for _ in range(testCount):
            len = ri(minLen, maxLen)
            k = ri(1, len)

            nums = [0] * len
            for i in range(len):
                nums[i] = ri(1, maxVal)        

            yield (nums, k)

def cornerCases():
    yield ([MAX_VAL] * MAX_N, 0)
    yield ([MAX_VAL] * MAX_N, MAX_N)
    yield ([i for i in range(1, MAX_N + 1)], 0)
    yield ([i for i in range(1, MAX_N + 1)], MAX_N)
    yield ([i // 2 + 1 for i in range(MAX_N)], MAX_N // 2 - 1)
    yield ([i % (MAX_N // 2) + 1 for i in range(MAX_N)], MAX_N // 2 - 1)


with open('test.txt', 'w') as file:
    random.seed(0)
    for tc in examples(): prtc(tc)
    for tc in smallCases(): prtc(tc)
    for tc in sorted(list(randomCases()), key = lambda x: len(x[0])): prtc(tc)
    for tc in cornerCases(): prtc(tc)

Solutions

Solution 1: Sliding 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}\).

Python3JavaC++GoTypeScriptRust

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

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;
    }
}

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;
    }
};

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
}

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;
}

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
    }
}

3641. Longest Semi-Repeating Subarray 🔒

Description

Solutions

Solution 1: Sliding Window

Comments