Java Solution Beats 100% KMP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int minValidStrings(String[] words, String target) {\n        int m = target.length();\n        int n = words.length;\n        ArrayList<int[]> arr = new ArrayList<>();\n        for(int i = 0; i < n; i++) {\n            StringBuilder sb = new StringBuilder();\n            sb.append(words[i]);\n            sb.append(\'#\');\n            sb.append(target);\n            int[] lps = new int[words[i].length() + m + 1];\n            kmp(lps, sb.toString());\n            arr.add(lps);\n        }\n        int total = 0;\n        int i = m - 1;\n        while(i >= 0) {\n            int mm = 0;\n            for(int j = 0; j < n; j++) {\n                mm = Math.max(mm, arr.get(j)[words[j].length() + 1 + i]);\n            }\n            if(mm == 0) return -1;\n            i -= mm;\n            total++;\n        }\n        return total;\n    }\n    public static void kmp(int[] lps, String s) {\n        int length = 0;\n        int i = 1;\n        while (i < s.length()) {\n            if (s.charAt(i) == s.charAt(length)) {\n                length++;\n                lps[i] = length;\n                i++;\n            } else {\n                if (length != 0) {\n                    length = lps[length - 1];\n                } else {\n                    lps[i] = 0;\n                    i++;\n                }\n            }\n        }\n    }\n}\n```
['Java']