Segement Tree + KMP +Dyanamic Programming
W=words.length();\nWi=words[i].length();\nT=target.length()\n\n# Complexity\n- Time complexity:O(sum(Wi)+W*T+Tlog(T))\n Add your time complexity here, e.g. O(n)
W=words.length();\nWi=words[i].length();\nT=target.length()\n\n# Complexity\n- Time complexity:O(sum(Wi)+W*T+Tlog(T))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(T + max(Wi))\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass SegmentTree{\n   \nvector<int> sgtree;\n\n  public:\n \n  SegmentTree(int n){\n     sgtree.resize(4*n+1);\n     \n     \n }\n \n \n void build(int index,int low,int high,vector<int> &arr){\n     if(low==high){\n         sgtree[index]=arr[low];\n         return ;\n     }\n     \n     int mid=(low+high)/2;\n     \n     build(2*index+1,low,mid,arr);\n     build(2*index+2,mid+1,high,arr);\n     \n     sgtree[index]=min(sgtree[2*index+1],sgtree[2*index+2]);\n     \n     \n }\n \n int query(int index,int low,int high,int l,int h){\n     if(low>h||l>high)\n     return 1e6;\n     \n    else if(l<=low&&high<=h)\n     return sgtree[index];\n     \n     \n     else{\n         int mid=(low+high)/2;\n         \n         return min(query(2*index+1,low,mid,l,h),query(2*index+2,mid+1,high,l,h));\n     }\n }\n \n void update(int index,int low,int high,int i,int val){\n     if(low==high){\n         sgtree[index]=val;\n         return ;\n     }\n     \n     int mid=(low+high)/2;\n     \n     if(i<=mid)\n     update(2*index+1,low,mid,i,val);\n     \n     else\n     update(2*index+2,mid+1,high,i,val);\n     \n     sgtree[index]=min(sgtree[2*index+1],sgtree[2*index+2]);\n }\n};\nclass Solution {\npublic:\n    vector<int> getlps(string s){\n         int m=s.size();\n\n     int i=1;\n     vector<int> lps(m,0);\n     int len=0;\n\n     lps[0]=0;\n     while(i<m){\n         if(s[i]==s[len]){\n             len++;\n             lps[i]=len;\n             i++;\n         }\n         else{\n             if(len>0){\n                 len=lps[len-1];\n             }\n             else{\n                 lps[i]=0;\n                 i++;\n             }\n         }\n     }\n\n     return lps;\n    }\n    int minValidStrings(vector<string>& words, string target) {\n\n        int m=target.size();\n        vector<int> v(m,0);\n        for(auto i:words){\n            auto lps=getlps(i+"#"+target);\n        //       for(auto i:lps)\n        // cout<<i<<" ";\n        // cout<<endl;\n            for(int j=0;j<m;j++){\n                v[j]=max(v[j],lps[j+(int)i.size()+1]);\n            }\n        }\n\n        // for(auto i:v)\n        // cout<<i<<" ";\n        // cout<<endl;\n\n        vector<int> dp(m+1,1e6);\n\n        dp[0]=0;\n\n        SegmentTree sg(m+1);\n\n        sg.build(0,0,m,dp);\n\n        for(int i=1;i<=m;i++){\n            int len=v[i-1];\n\n            int mini=sg.query(0,0,m,i-len,i-1);\n\n            dp[i]=1+mini;\n\n            sg.update(0,0,m,i,dp[i]);\n        }\n\n          return (dp[m]>=1e6)?-1:dp[m];\n    }\n};\n```
['String', 'Dynamic Programming', 'Segment Tree', 'String Matching', 'C++']