Java Prefix Sum + All Substrings
Time: O(n^2)\n\nimport java.sql.Array;\nimport java.util.*;\n\npublic class Solution {\n\n    public int countDistinct(int[] nums, int k, int p) {\n        int 
Time: O(n^2)\n```\nimport java.sql.Array;\nimport java.util.*;\n\npublic class Solution {\n\n    public int countDistinct(int[] nums, int k, int p) {\n        int []pSum = new int[nums.length + 1];\n\t\t// how many at interview (0, i) are divisible by p\n        for(int i = 0; i<nums.length; i++) {\n            if(i == 0) {\n                if(nums[i] % p == 0) {\n                    pSum[i + 1] = 1;\n                }\n            } else {\n                if(nums[i] % p == 0) {\n                    pSum[i + 1] = pSum[i] + 1;\n                } else {\n                    pSum[i + 1] = pSum[i];\n                }\n            }\n        }\n\t\t// count all unique valid subsets. Subset (i, j) is valid  if pSum(i, j) <= k\n        int n = nums.length;\n        Set<List<Integer>> distinctAnswers = new HashSet<>();\n        for(int i = 0; i< n; i++) {\n            List<Integer> cur = new ArrayList<>();\n            for(int j = i; j<n; j++) {\n                cur.add(nums[j]);\n                if(pSum[j + 1] - pSum[i] > k) {\n                    break;\n                }\n\n                distinctAnswers.add(new ArrayList<>(cur));\n            }\n        }\n\n        return distinctAnswers.size();\n    }\n\n}\n\n```
['String', 'Prefix Sum', 'Java']