Leetcode 992 Subarray with k different integers about leetcode-solutions HOT 1 CLOSED

1. There are at most O(n^2) distinct subarrays if all elemtents are distinct odds and k is n, then the worst case of complexity would be at least O(n^2).
2. Most solutions in your link are O(n^3), which are not really O(n) or O(n^2) as they claimed.
3. Here I provide a simple and real O(n^2) solution which is extended from 992 Subarrays with K Different Integers as you wished:

# Time:  O(n^2)
# Space: O(t), t is the size of trie

import collections


class Solution(object):
    def distinctSubarraysWithAtMostKOddIntegers(self, A, K):
        def countDistinct(A, left, right, trie):  # Time: O(n), Space: O(t)
            result = 0
            for i in reversed(xrange(left, right+1)):
                if A[i] not in trie:
                    result += 1
                trie = trie[A[i]]
            return result
        
        _trie = lambda: collections.defaultdict(_trie)
        trie = _trie()
        result, left, count = 0, 0, 0
        for right in xrange(len(A)):
            count += A[right]%2
            while count > K:
                count -= A[left]%2
                left += 1
            result += countDistinct(A, left, right, trie)
        return result

4. Another solution may be like what zed_b and TheSithPadawan said in the link:
   • Find all distinct subarrays by building suffix tree in O(n^2), which could be improved by Ukkonen's Algorithm in O(nlogd), where d is the number of distinct integers
   • Traverse the suffix tree until all paths with at most k odd elements are visited in O(r)
   • Time: O(nlogd + r), r is the number of the result, which is between O(1) ~ O(n^2), thus total time is at best Ω(nlogd), and at worst O(n^2)
   • Space: O(nd)

from leetcode-solutions.