Distinct Subarrays with at most k odd elements II

In this solution, we try to generate all subarrays and check if the subarray contains at most K odd elements or not. Also, we will build a HashSet of the subarray to check if any subarray is already in the HashSet or not. If the subarray contains at most K odd elements and it is not present in the HashSet then we will increment our answer by 1.

Steps: 

• Declare a variable to store the count of distinct subarrays with at most K odd elements, say answer.
• Create a HashSet to check whether we have included this subarray in our answer or not.
• Run two nested loops to generate all subarrays.
• If any subarray has a count of odd elements <= K and is not present in a HashSet then increment answer by 1 i.e., do answer += 1.
• At last, we return the answer.

The idea is here to maintain a sliding window that will contain at most K odd elements and if odd elements in the window become greater than K then we will pop elements from the front until we will make a window in which will contain at most K odd elements.

Steps :

• Declare a variable to store the count of distinct subarrays with at most K odd elements, say answer, and currentOdd to store count of odd elements in the current subarray.
• Initialize two pointers left = 0, right = 0 and currentOdd = 0.
• Declare a deque to store keep track of elements in the current subarray, say currentWindow.
• Run a loop for all indices i.e. from i =0 to size of the array, and do:
  • Initialize right with i.
  • Insert current element i.e. arr[i] to currentWindow.
  • If the current element is odd then increment the count of current odd elements by 1 i.e. do currentOdd+=1.
  • Find left most valid index of the window for current right i.e. keep popping elements from the front of deque until currentOdd becomes at most k.
  • Add all valid subarrays to answer by checking if it already presents in the Hash set or not. If the subarray is not present HashSet then add this subarray into the hash set and increment answer by 1.
• Finally, return the answer.

In this approach, we will use a suffix array and longest common prefix(LCP) array to count unique subarrays which contain no more than k odd elements. Also, we will optimize the solution with the help of the boundaryArray that will tell us whether or not it will exceed k odd elements after the addition of more elements in the current subarray.
 

Boundary Array: Boundary array will store right boundary for each index for at most k odd elements

Suffix Array: Suffix Array will store all the sorted suffixes of array ‘ARR’’.

LCP array: Each index of LCP array will store how many elements two sorted suffixes have in common.

Unique subarrays = (total subarrays having k unique elements - duplicates), where

duplicates = sum of elements in LCP array.
 

Steps :

• Initialize a variable boundaryArray. Get boundary array using getOddBoundary function and store it in boundaryArray.
• Initialize a variable lcpArray. Get LCP array using getLcpArray function and store it in lcpArray..
• Initialize a variable suffixArray. Get suffix array using getSuffixArray function and store it in suffixArray.
• Initialize a variable ans with value 0.
• Iterate i in 0 to n.
  • ans += min(boundaryArray[suffixArray[i]], n) - suffixArray[i].
• Iterate i in 0 to (n - 1)
  • ans -= min(boundaryArray[suffixArray[i]] - suffixArray[i], lcpArray[i]).
• Finally return ans.

getOddBoundary(vector <int> &v, int n, int k)

• Initialize a vector ret.
• Iterate i in n - 1 to 0.
  • Set k as (k - v[i] % 2)
  • Iterate while k is less than 0.
    • Set k as (k + v[j--] % 2)
  • Set ret[i] as j + 1
• Return ret
   

getLcpArray(vector <int> &s)

• Initialize a variable n to store size of vector s.
• Initialize a vector suffixArray. Get boundary array using getSuffixArray function and store it in suffixArray.
• Intialize a vector rank.
• Iterate i in 0 to n
  • Set rank[suffixArray[i]] as i.
• Initialize a vector lcp.
• Iterate i in 0 to n. Also declare h = 0.
  • If rank[i] is less than n - 1
    • Iterate j = suffixArray[rank[i] + 1], while s[i + h] == s[j + h], increment h by 1.
    • Set lcp[rank[i]] as h
    • If h > 0, decrement h by 1.
• Return lcp.

getSuffixArray(vector <int> &S)

• Initialize a variable n to store size of vector S.
• Initialize a vector suffixArray.
• Iterate i in n-1 to 0
  • Push i to suffixArray.
• Stable sort suffixArray according to vector S.
• Initiaize a vector classes.
• Iterate i in 0 to n
  • Set classes[i] as S[i]
• Iterate len in 1 to n
  • Initialize a vector c. Copy vector classes to c.
  • Iterate i in 0 to n.
  • Set classes[suffixArray[i]] as ( i > 0 && c[suffixArray[i - 1]] == c[suffixArray[i]] && suffixArray[i - 1] + len < n && c[suffixArray[i - 1] + len / 2] == c[suffixArray[i] + len / 2] ? classes[suffixArray[i - 1]] : i).
• Initialize a vector cnt.
• Assign every element in cnt at cnt[i] = i , where i belongs to [0,n-1]
• Initialize a vector s. Copy vector suffixArray to s.
• Iterate i in 0 to n
  • Initialize a variable s1 as s[i] - len.
  • If s1 is greater than or equal to 0
    • Set suffixArray[cnt[classes[s1]]++] as s1.
• Return suffixArray.