Three solutions: Trie, Rabin-Karp + Set, LCP-array O(N) time, O(N) space
First solution (Trie)\nWe use a trie to compactly store all possible subarrays.\n When we find out that the prefix doesn\'t exist, we increment answer and creat
# First solution (Trie)\nWe use a trie to compactly store all possible subarrays.\n When we find out that the prefix doesn\'t exist, we increment answer and create another node in the tree\n```\nimport java.util.ArrayList;\nimport java.util.List;\n\npublic class Solution {\n    private static final int MAX_P = 200;\n\n    public int countDistinct(int[] nums, int k, int p) {\n        int n = nums.length;\n        List<int[]> child = new ArrayList<>();\n        child.add(new int[MAX_P + 1]);\n        int nxt = 1, ans = 0;\n        for (int i = 0; i < n; i++) {\n            int count = 0, node = 0;\n            int j = i;\n            while (j < n && count <= k) {\n                int c = nums[j++];\n                if (c % p == 0) if (count++ == k) break;\n                if (child.get(node)[c] == 0) {\n                    ans++;\n                    child.get(node)[c] = nxt++;\n                    child.add(new int[MAX_P + 1]);\n                }\n                node = child.get(node)[c];\n            }\n        }\n        return ans;\n    }\n}\n```\n\nThis solution has O(N^2) space complexity and O(N^2) time complexity. \n\n# Rabin-Karp Rolling Hash\nWe use some incremental hashing function as we don\'t want to recalculate it for every possible subarray.\nI took as mod the largest prime number below `(Long.MAX_VALUE-200)/201`, so the hash calculation never overflows.\nThis solution has drawbacks and it depends on some luck, cause it doesn\'t check any hash collisions.\n```\npublic class Solution {\n    private static final int MAX_P = 200;\n    private static final long base = MAX_P + 1;\n    private static final long mod = 45887423068929227L;\n\n    public int countDistinct(int[] nums, int k, int p) {\n        int n = nums.length;\n        Set<Long> set = new HashSet<>();\n        for (int i = 0; i < n; i++) {\n            long hash = 0;\n            for (int j = i, count = 0; j < n; j++) {\n                if (nums[j] % p == 0) if (count++ == k) break;\n                hash = (hash * base + nums[j]) % mod;\n                set.add(hash);\n            }\n        }\n        return set.size();\n    }\n}\n```\nThis solution also has O(N^2) time complexity and O(N^2) space complexity.\n\n\n# Suffix Array and Longest Common Prefix Array\nConstruction of Suffix Arrays is pretty hard theme, so I won\'t explain it here, but the listing of algos can be seen in appendix. You can read more about Suffix Arrays Construction at other resources.\n\nWe build suffix array, lcp-array and also for each position we calculate what is the longest valid string can start from this index.\nFor each element we calculate additional strings it can form. But we remember that some of this strings can be added also by the next element in the suffix array.\n\n```\npublic class Solution {\n    private static final int MAX_P = 200;\n\n    public int countDistinct(int[] nums, int k, int p) {\n        int n = nums.length;\n        if (n == 0) return 0;\n        if (n == 1) {\n            if (k >= 1 || nums[0] % p != 0) return 1;\n            else return 0;\n        }\n        int[] maxLength = new int[n];\n        for (int l = n - 1, r = n, count = 0; l >= 0; l--) {\n            if (nums[l] % p == 0) {\n                count++;\n                while (count > k) if (nums[--r] % p == 0) count--;\n            }\n            maxLength[l] = r - l;\n        }\n\n        int[] suffixArray = buildSuffixArray(nums, MAX_P);\n        int[] invSuffixArray = inverseSuffixArray(suffixArray);\n        int[] lcp = buildLongestCommonPrefixArray(nums, suffixArray, invSuffixArray);\n\n        int ans = maxLength[suffixArray[n - 1]];\n        for (int sortedPos = n - 2; sortedPos >= 0; sortedPos--) {\n            int maxLen = maxLength[suffixArray[sortedPos]];\n            int commonLength = lcp[sortedPos];\n            if (commonLength < maxLen) ans += maxLen - commonLength;\n        }\n        return ans;\n    }\n}\n```\n\nThis solution has O(N) time complexity and O(N) space compelxity.\n\n# Appendix\nUsed algo:\nK\xE4rkk\xE4inen, Sanders algorithm to build suffix array in O(n)\nKasai, Arimura, Arikawa, Lee, Park algorithm to build LCP array in O(n)\n\n```\n\t// arr.length>=2, s[i]>=1, s[i]<=K\n    private static int[] buildSuffixArray(int[] arr, int K) {\n        int n = arr.length;\n        int[] s = Arrays.copyOf(arr, n + 3);\n        int[] SA = new int[n];\n        suffixArray(s, SA, n, K);\n        return SA;\n    }\n\n    private static int[] inverseSuffixArray(int[] suffixArray) {\n        int n = suffixArray.length;\n        int[] ans = new int[n];\n        for (int i = 0; i < n; i++) ans[suffixArray[i]] = i;\n        return ans;\n    }\n\n    private static int[] buildLongestCommonPrefixArray(int[] arr, int[] suffixArray, int[] invSuffixArray) {\n        int n = arr.length;\n        int[] lcp = new int[n - 1];\n        int k = 0;\n        for (int i = 0; i < n; i++) {\n            if (k > 0) k--;\n            if (invSuffixArray[i] == n - 1) {\n                k = 0;\n            } else {\n                int j = suffixArray[invSuffixArray[i] + 1];\n                while (i + k < n && j + k < n && arr[i + k] == arr[j + k]) k++;\n                lcp[invSuffixArray[i]] = k;\n            }\n        }\n        return lcp;\n    }\n\n    //Lexicographic order for pairs.\n    private static boolean leq(int a1, int a2, int b1, int b2) {\n        return (a1 < b1 || (a1 == b1 && a2 <= b2));\n    }\n\n    //Lexicographic order for triples.\n    private static boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) {\n        return (a1 < b1 || (a1 == b1 && leq(a2, a3, b2, b3)));\n    }\n\n    private static void suffixArray(int[] s, int[] SA, int n, int K) {\n        int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;\n        int[] s12 = new int[n02 + 3], SA12 = new int[n02 + 3], s0 = new int[n0], SA0 = new int[n0];\n\n        for (int i = 0, j = 0; i < n + (n0 - n1); i++) if (i % 3 != 0) s12[j++] = i;\n\n        radixPass(s12, SA12, s, 2, n02, K);\n        radixPass(SA12, s12, s, 1, n02, K);\n        radixPass(s12, SA12, s, 0, n02, K);\n\n        // find lexicographic names of triples\n        int name = 0, c0 = -1, c1 = -1, c2 = -1;\n        for (int i = 0; i < n02; i++) {\n            if (s[SA12[i]] != c0 || s[SA12[i] + 1] != c1 || s[SA12[i] + 2] != c2) {\n                name++;\n                c0 = s[SA12[i]];\n                c1 = s[SA12[i] + 1];\n                c2 = s[SA12[i] + 2];\n            }\n            if (SA12[i] % 3 == 1) {\n                s12[SA12[i] / 3] = name;\n            } // left half\n            else {\n                s12[SA12[i] / 3 + n0] = name;\n            } // right half\n        }\n\n        // recurse if names are not yet unique\n        if (name < n02) {\n            suffixArray(s12, SA12, n02, name);\n            // store unique names in s12 using the suffix array\n            for (int i = 0; i < n02; i++) s12[SA12[i]] = i + 1;\n        } else // generate the suffix array of s12 directly\n            for (int i = 0; i < n02; i++) SA12[s12[i] - 1] = i;\n\n        // stably sort the mod 0 suffixes from SA12 by their first character\n        for (int i = 0, j = 0; i < n02; i++) if (SA12[i] < n0) s0[j++] = 3 * SA12[i];\n        radixPass(s0, SA0, s, 0, n0, K);\n\n        // merge sorted SA0 suffixes and sorted SA12 suffixes\n        for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {\n            int i = getI(SA12, n0, t); // pos of current offset 12 suffix\n            int j = SA0[p]; // pos of current offset 0 suffix\n            if (SA12[t] < n0 ? // different compares for mod 1 and mod 2 suffixes\n                    leq(s[i], s12[SA12[t] + n0], s[j], s12[j / 3]) :\n                    leq(s[i], s[i + 1], s12[SA12[t] - n0 + 1], s[j], s[j + 1], s12[j / 3 + n0])\n            ) {// suffix from SA12 is smaller\n                SA[k] = i;\n                t++;\n                if (t == n02) // done --- only SA0 suffixes left\n                    for (k++; p < n0; p++, k++) SA[k] = SA0[p];\n            } else {// suffix from SA0 is smaller\n                SA[k] = j;\n                p++;\n                if (p == n0) // done --- only SA12 suffixes left\n                    for (k++; t < n02; t++, k++) SA[k] = getI(SA12, n0, t);\n            }\n        }\n    }\n\n    private static int getI(int[] SA12, int n0, int t) {\n        return SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2;\n    }\n\n    private static void radixPass(int[] a, int[] b, int[] r, int shift, int n, int K) {\n        int[] c = new int[K + 1]; // counter array\n        for (int i = 0; i < n; i++) c[r[a[i] + shift]]++; // count occurrences\n        for (int i = 0, sum = 0; i <= K; i++) { // exclusive prefix sums\n            int t = c[i];\n            c[i] = sum;\n            sum += t;\n        }\n        for (int i = 0; i < n; i++) b[c[r[a[i] + shift]]++] = a[i];\n    }\n```\n\n
['Two Pointers', 'Suffix Array', 'Java']