2958. Length of Longest Subarray With at Most K Frequency

leetcode-2958-longest-subarray.java

import java.util.HashMap;

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int N = nums.length;

        int left = 0, right = 0, f, x;
        int result = 1, cur;
        HashMap<Integer, Integer> freq = new HashMap<>();

        while ( left <= right && right < N ) {
            x = nums[right];

            if ( freq.containsKey( x ) ) {
                f = freq.get( x );

                if ( f == k ) {
                    result = Math.max( result, right - left );

                    // @todo Improve TC by maintaining a linked list (of max length k) for each unique array item which has the previous k indexes where the item occured
                    while ( nums[left] != nums[right] ) {
                        freq.put( nums[left], freq.get( nums[left] ) - 1 );
                        ++left;
                    }

                    ++left;
                } else {
                    freq.put( x, 1 + f );
                }
            } else {
                freq.put( x, 1 );
            }
            
            ++right;
        }

        cur = right - left;
        if ( cur > result ) {
            result = cur;
        }

        return result;
    }
}