Easy Explanation of KMP approach✔✔🙌 beats 💯 %.
Intuition\nMake use of KMP algorithm to reduce time complexity to avoid TLE.\n\n# Approach\nAs the constraints are pretty high here as compared to its first par
# Intuition\nMake use of KMP algorithm to reduce time complexity to avoid **TLE**.\n\n# Approach\nAs the constraints are pretty high here as compared to its first part, we nee to think of an approach which can be solved in time complexity below O(n^2). Where comes a concept of **KMP** algorithm. where we kind of precomputes the lps(**longest prefix sufix**) which helps in utilizing this lps information further and solve the problem.   \n\n# Complexity\n- Time complexity: O(O(sum(word lengths) + ("#" used) + (length of words) * target length) + O(target length * length of words)) => max(O(n+100+100 * m) , O(m * 100)) ~ **O(n+m)**;\n\n- Space complexity: O(sum(word lengths) + ("#" used) + (length of words) * target length) => O(n+100+100 * m) ~ **O(n+m)**; \n\n# Code\n```java []\nclass Solution {\n    private int[] kmp(String s){\n        int n = s.length();\n        int lps[] = new int[n];\n        int pL = 0;\n        \n        int i = 1;\n        while(i<n){\n            if(s.charAt(i) == s.charAt(pL)){\n                lps[i] = pL + 1;\n                pL = lps[i];\n                i++;\n            }\n            else {\n                if(pL == 0){\n                    lps[i] = 0;\n                    i++;\n                }\n                else{\n                    pL = lps[pL-1]; \n                }\n            }\n        }\n\n        return lps;\n    }\n\n\n    public int minValidStrings(String[] words, String target) {\n        List<int[]> arr = new ArrayList();\n        for(String word : words)arr.add(kmp(word+"#"+target));\n        int res = 0;\n        int i = target.length()-1;\n        \n        while(i >= 0){\n            int maxLen = 0;\n            for(int j=0;j<words.length;j++){\n                maxLen = Math.max(maxLen, arr.get(j)[words[j].length() + 1 + i]);\n            }\n            if(maxLen == 0)return -1;\n            i -= maxLen;\n            res++;\n        }\n\n        return res;\n    }\n}\n```
['Two Pointers', 'String', 'String Matching', 'Java']