/*
 * 演算法 / Algorithm: 滑動視窗 + 自製雜湊表 (Sliding window + hand-written hash map).
 * 用左右指針框出目前視窗，雜湊表記錄每個值在視窗內的出現次數。
 * Right pointer grows the window; when the just-added value's count exceeds k,
 * advance left until it's valid again. Answer is the largest window length seen.
 * 時間 O(n)，空間 O(n)。Time O(n), space O(n).
 */

#include <stdlib.h>   // malloc, calloc, free (動態記憶體 / dynamic memory)

/* --- 一個極簡的「值 -> 次數」開放定址雜湊表 --- */
/* --- A minimal open-addressing hash map from value -> count --- */
typedef struct {
    long *keys;    // 存放鍵（也就是 nums 的值）/ stores keys (the nums values)
    int  *vals;    // 對應的計數 / the matching counts
    char *used;    // 該格是否已被占用 (1=用了, 0=空) / is this slot occupied
    int   cap;     // 桶子總數，取 2 的次方方便用位元遮罩取模 / bucket count, a power of two
} Map;

// 建立一個容量為 cap 的雜湊表 / build a hash map with capacity cap
static Map map_new(int cap) {
    Map m;
    m.cap  = cap;                        // 記住容量 / remember capacity
    m.keys = malloc(sizeof(long) * cap); // 配置鍵陣列 / allocate keys array
    m.vals = calloc(cap, sizeof(int));   // calloc 會把計數清成 0 / calloc zeroes the counts
    m.used = calloc(cap, sizeof(char));  // calloc 把 used 全設為 0=空 / all slots start empty
    return m;
}

// 用完後釋放記憶體，避免記憶體洩漏 / free memory afterwards to avoid leaks
static void map_free(Map *m) {
    free(m->keys);  // 釋放鍵陣列 / free keys
    free(m->vals);  // 釋放值陣列 / free vals
    free(m->used);  // 釋放占用旗標 / free used flags
}

// 找到 key 該待的桶子索引 (若不存在則回傳一個空桶) / find the slot for key (or an empty one)
static int map_slot(Map *m, long key) {
    // 用位元 AND 取代取模：因為 cap 是 2 的次方，key & (cap-1) 等同 key % cap
    // Bitwise AND as a fast modulo: since cap is a power of two, key & (cap-1) == key % cap
    int i = (int)(((unsigned long)key * 1000000007UL) & (m->cap - 1));
    // 線性探測：若桶子被別的鍵占用，就看下一格 / linear probing to next slot on collision
    while (m->used[i] && m->keys[i] != key) {
        i = (i + 1) & (m->cap - 1);      // 前進一格並回繞到頭 / step forward, wrap around
    }
    return i;                            // 回傳最終落腳的桶子 / return the resting slot
}

// 把 key 的計數加上 delta（可為 +1 或 -1），並回傳更新後的計數
// Add delta (+1 or -1) to key's count, return the new count
static int map_add(Map *m, long key, int delta) {
    int i = map_slot(m, key);            // 找到桶子 / locate the slot
    if (!m->used[i]) {                   // 若這是第一次遇到這個 key / first time we see this key
        m->used[i] = 1;                  // 標記占用 / mark occupied
        m->keys[i] = key;                // 寫入鍵 / store the key
        m->vals[i] = 0;                  // 計數從 0 開始 / count starts at 0
    }
    m->vals[i] += delta;                 // 更新計數 / update the count
    return m->vals[i];                   // 回傳新計數給呼叫者判斷 / return new count to caller
}

int maxSubarrayLength(int* nums, int numsSize, int k) {
    // 桶子數取大於 2*numsSize 的最小 2 次方，確保夠鬆、探測快
    // Pick a power-of-two capacity comfortably larger than the data to keep probing fast
    int cap = 1;
    while (cap < numsSize * 2) cap <<= 1; // cap 左移一位就是乘 2 / left shift doubles cap
    Map count = map_new(cap);            // 建立計數表 / build the count map

    int left = 0;                        // 視窗左端點 / window's left boundary
    int ans  = 0;                        // 目前最長好子陣列的長度 / best length so far

    // right 是視窗右端點，一步步向右擴張 / right pointer expands the window one step at a time
    for (int right = 0; right < numsSize; right++) {
        // 把新元素加入視窗，計數 +1，並拿到它的新頻率
        // Add the new element into the window (+1) and read back its new frequency
        int freq = map_add(&count, nums[right], +1);

        // 只有「剛加入的這個值」可能超標；若超過 k 就從左邊縮小視窗
        // Only the just-added value can break the rule; if it exceeds k, shrink from the left
        while (freq > k) {
            // 移除最左邊元素：計數 -1，然後 left 右移 / drop leftmost: count -1, then advance left
            map_add(&count, nums[left], -1);
            left++;                      // 左端點右移，視窗變小 / move left boundary rightwards
            // 重新讀取「剛加入值」目前的頻率，看看是否已合法
            // Re-check the just-added value's current frequency to see if it's now legal
            freq = map_add(&count, nums[right], 0); // delta=0 表示只查詢不改動 / delta 0 = query only
        }

        // 到這裡視窗一定合法；用它的長度更新答案 / window is valid now; update the answer
        int len = right - left + 1;      // 視窗長度 = 右 - 左 + 1 / window length
        if (len > ans) ans = len;        // 取較大者 / keep the maximum
    }

    map_free(&count);                    // 釋放雜湊表記憶體 / free the hash map
    return ans;                          // 回傳最長好子陣列的長度 / return the answer
}