KMP + INTERVAL OVERLAPING
Intuition\nThe task involves finding the minimum number of words from a list that, when concatenated or overlapped, can cover a target string. The solution uses
# Intuition\nThe task involves finding the minimum number of words from a list that, when concatenated or overlapped, can cover a target string. The solution uses the KMP (Knuth-Morris-Pratt) string matching algorithm to efficiently search for all the occurrences of each word in the target string. Then, it handles interval overlapping to determine the minimum number of word fragments required to cover the entire target string.\n\n# Approach\nLPS (Longest Prefix Suffix) Calculation:\n\nFirst, we preprocess each word in the list using the LPS array from the KMP algorithm. The LPS array helps to skip unnecessary comparisons during the string matching process.\nMatching words to the target:\n\nFor each word in the list, we use the KMP algorithm to find its occurrences in the target string. Every time a match is found or the pattern can\'t we match any further we save interval (index on target), in which some prefix of patter was matched , we record its start and end positions in an interval.\nHandling Interval Overlapping:\n\nOnce we have all the intervals (start and end positions of matched word fragments), we sort them based on their starting positions. Then, we try to cover the target string by merging these intervals, aiming to minimize the number of word fragments used to cover the entire target.\nFinal Result:\n\nThe algorithm traverses through the intervals and checks if it\'s possible to cover the entire target string with them. If yes, it returns the minimum number of fragments needed. Otherwise, it returns -1 indicating it\'s impossible to cover the target string.\n# Complexity\n# Time Complexity:\n\nPreprocessing (LPS array calculation) for each word takes O(m) where m is the length of the word.\nMatching each word with the target string takes O(n) where n is the length of the target string.\nSorting the intervals takes O(k log k) where k is the number of intervals.\nOverall time complexity: O(n * m + k log k).\nSpace Complexity:\n\nStoring LPS arrays for each word takes O(n * m).\nStoring intervals takes O(k), where k is the number of matches.\nOverall space complexity: O(n * m + k).\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    // Function to calculate the LPS array for a given string using KMP preprocessing\n    void lpscal(string& s, vector<int> lps[], int n) {\n        int m = s.size();\n        int i = 0;  // Length of the previous longest prefix suffix\n        lps[n].resize(m, 0);  // Initialize LPS array for this word\n        lps[n][0] = 0;  // LPS of first character is always 0\n        int j = 1;  // Start from the second character\n\n        // Build the LPS array\n        while (j < m) {\n            if (s[i] == s[j]) {\n                i++;  // Increase the prefix length\n                lps[n][j] = i;  // Assign LPS value\n                j++;\n            } else if (i != 0)\n                i = lps[n][i - 1];  // Move to the last matched prefix\n            else\n                j++;\n        }\n    }\n\n    // Function to find matches of word \'p\' in the target \'t\' using the LPS array\n    void match(string& p, string& t, vector<int> lps[], int x, vector<vector<int>>& inter) {\n        int n = t.size();\n        int m = p.size();\n        int i = 0;  // Pointer for target string\n        int j = 0;  // Pointer for word string\n\n        // Perform the matching\n        while (i < n) {\n            if (t[i] == p[j]) {\n                i++;\n                j++;\n            } else {\n                // When mismatch occurs, update the pointers\n                if (j != 0) {\n                    inter.push_back({i - j, i - 1});  // Store the match interval\n                    j = lps[x][j - 1];  // Jump to the previous LPS value\n                } else\n                    i++;\n            }\n\n            // If a full match of word \'p\' is found\n            if (j == m) {\n                inter.push_back({i - j, i - 1});  // Store the interval\n                j = lps[x][j - 1];  // Jump to the next possible match\n            }\n        }\n\n        // If some part of the word is still matched at the end of the target string\n        if (j != m && i - 1 >= i - j)\n            inter.push_back({i - j, i - 1});\n    }\n\n    // Main function to find the minimum number of words to cover the target string\n    int minValidStrings(vector<string>& words, string target) {\n        int n = words.size();\n        vector<int> lps[n];  // LPS arrays for each word\n\n        // Preprocess all words and compute their LPS arrays\n        for (int i = 0; i < n; i++) {\n            lpscal(words[i], lps, i);\n        }\n\n        vector<vector<int>> inter;  // Store intervals of matches (start, end)\n\n        // Find matching intervals for each word in the target string\n        for (int i = 0; i < n; i++) {\n            match(words[i], target, lps, i, inter);\n        }\n\n        // Sort intervals based on their start positions\n        sort(inter.begin(), inter.end(), [](vector<int>& a, vector<int>& b) {\n            return a[0] < b[0];\n        });\n\n        int ans = 0;  // Store the answer (minimum number of words)\n        int end = -1;  // Track the last covered position in the target\n        int k = inter.size();\n        int t = target.size();\n\n        // If no intervals are found, return -1\n        if (k == 0)\n            return -1;\n\n        int i = 0;\n\n        // Try to cover the entire target using the intervals\n        while (i < k && end < t - 1) {\n            int j = i;\n            int temp = -1;  // Track the farthest position we can cover\n            while (j < k && inter[j][0] <= end + 1) {\n                temp = max(temp, inter[j][1]);\n                j++;\n            }\n\n            // If no further progress can be made, return -1\n            if (temp == -1)\n                return -1;\n\n            ans++;  // Increment the count of words used\n            end = temp;  // Update the last covered position\n            i = j;  // Move to the next interval\n        }\n\n        // Return the result if the target is fully covered, else return -1\n        return end >= t - 1 ? ans : -1;\n    }\n};\n\n```
['C++']