[Java] Trie vs Sliding Window | With Explanation
Trie Approach\n##### Steps\n1. For every index i in nums, insert nums[i,n-1] to the trie\n2. During the insertion, check if it\'s valid (at most k elements divi
### Trie Approach\n##### Steps\n1. For every index `i` in `nums`, insert `nums[i,n-1]` to the trie\n2. During the insertion, check if it\'s valid (at most k elements divisible by p)\n3. If the `trie.next` doesn\'t exist, increase the count because this subarray never visited\n4. Finally, sum up the count\n\n##### Solution\n- time: `O(n^2)`\n- space: `O(n^2)`\n```java\nclass Trie {\n    Trie[] next = new Trie[201];\n}\n\npublic int countDistinct(int[] nums, int k, int p) {\n    int n = nums.length, count = 0;\n    Trie t = new Trie();\n    for (int i = 0; i < n; i++) {\n        count += insert(t, nums, i, k, p);\n    }\n    return count;\n}\n\nint insert(Trie t, int[] nums, int start, int k, int p) {\n    int n = nums.length, count = 0;\n    for (int i = start; i < n; i++) {\n        int num = nums[i];\n\n        if (num % p == 0) k--;\n        if (k < 0) return count;\n        if (t.next[num] == null) {\n            t.next[num] = new Trie();\n            count++;\n        }\n        t = t.next[num];\n    }\n    return count;\n}\n```\n\n### Sliding Window Approach\n##### Steps\n1. Move the right pointer `i` to check the subarray with tail at `i`\n2. By moving left pointer `j`, we can get the longest valid `subarray(j,i)`\n3. Add all valid subarrays with tail at `i`  to a set\n4. Finally, the size of set is the result\n\n##### Solution\n- time: `O(n^2)`\n- space: `O(n^2)`\n```java\npublic int countDistinct(int[] nums, int k, int p) {\n    int n = nums.length, j = 0, count = 0;\n    Set<String> res = new HashSet<>();\n\n    for (int i = 0; i < n; i++) {\n        if (nums[i] % p == 0) count++;\n\n        while (count > k) {\n            if (nums[j++] % p == 0) count--;\n        }\n        Set<String> set = tailSubstrings(nums, j, i);\n        res.addAll(set);\n    }\n    return res.size();\n}\n\nSet<String> tailSubstrings(int[] nums, int start, int end) {\n    Set<String> set = new HashSet<>();\n    StringBuilder sb = new StringBuilder();\n    for (int i = end; i >= start; i--) {\n        sb.append(nums[i]).append(",");\n        set.add(sb.toString());\n    }\n    return set;\n}\n```\n\nPlease let me know if you have questions or better solutions. Thanks :)
['Java']