Beats 99.7% | No hashing or Trie |sliding window | Longest common substring | DP
Maintain an array lcs[n][n]. lcs[i][j] gives longest common substring starting at i and j in the same array.\n\nVector dp is created where dp[[i] = max(dp[k][j]
Maintain an array lcs[n][n]. lcs[i][j] gives longest common substring starting at i and j in the same array.\n\nVector dp is created where dp[[i] = max(dp[k][j]) (0<=k and k<=i-1) it is created to see if there exists an index i such that i and j have a common substring length greater than a particular value.\n\nApply sliding window from length = 1 to length = n. and use the dp array to check for distinct arrays\n\n\n    \n    int countDistinct(vector<int>& nums, int k, int p) {\n        int n = nums.size();\n        vector < vector <int> > lcs(n+1, vector <int> (n+1));\n        lcs[n][n] = 0;\n        \n        for(int j=n; j>=0; j--)\n        {\n            for(int i = j; i>=0; i--)\n            {\n                if(j==n) lcs[i][j] = 0;\n                else\n                {\n                    if(nums[i] == nums[j])\n                        lcs[i][j] = 1 + lcs[i+1][j+1];\n                    else\n                        lcs[i][j] = 0;\n                }\n            }\n        }\n        \n        vector <int> dp(n+1);\n        \n        for(int j=0; j<n; j++)\n        {\n            int temp = 0;\n            for(int i=0; i<j; i++)\n                dp[j] = max(dp[j], lcs[i][j]);\n        }\n        \n        int ans = 0;\n        for(int len = 1; len <= n; len++)\n        {\n            int cnt = 0;\n            int lo = 0, hi = len-1;\n            for(int i = lo; i<=hi; i++)\n            {\n                if(nums[i]%p==0) cnt++;\n            }\n            if(cnt <= k) ans++;\n            while(hi+1 < n)\n            {\n                hi = hi+1;\n                if(nums[lo] % p == 0) cnt--;\n                if(nums[hi] % p == 0) cnt++;\n                lo++;\n                \n                if(cnt <= k && dp[lo] < len)\n                    ans++;\n            }\n            \n        }\n        return ans;\n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n    }\n};\n
['Dynamic Programming', 'C++']