2401: Longest-Nice-Subarray
Medium

I mean, you read “a subarray is a contiguous part of an subarray” and you should probably be thinking about sliding windows.

The key logic to this algorithm is realising that, given that we have a nice subarray of length n-1, to check whether adding a nth element would keep the subarray nice, instead of using bitwise AND on all possible pairs, we can instead XOR all elements and AND it with the nth element to check whether the subarray will still be nice.

Then, paired with the sliding window technique, we can basically just keep track of the XOR of all elements inside the subarray with a variable like val. That means, whenever we increment the left or right pointer, l and r, to shrink/expand the window, we just need XOR the value present at that index to “remove”/“add” it to val for comparing future elements.

code

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int ans = 0;
        int val = 0;
        int l = 0, r = 0;
        for (; l < nums.size() && r < nums.size(); ++l) {
            for(; r < nums.size() && ((val & nums[r]) == 0); ++r) {
                val ^= nums[r];
            }
            ans = max(ans, r-l);
            val ^= nums[l];
        }
        return ans;
    }
};

complexity

time taken