JAVA || Beats 100% || String Hashing + DP
Intuition\n Describe your first thoughts on how to solve this problem. \nSum of all strings length <= 10^5 so we would hash all strings and store all prefix of 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSum of all strings length <= 10^5 so we would hash all strings and store all prefix of each string in HashSet<Index> set, then apply dp.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nin function \'fun\', firstly find maximum length that can be found from ith position using binary seach on length and checking its hash value in HashSet<Index> set.\n\nLet max length = yaha that means using one operation we can go from i to any position x <= yaha then finding required operations from x.\n\nConcept of limit : just to reduce time complexity -> limit indicates that minimum position we would travel to avoid multiple unnecessary function calls. eg-> suppose we can go from 1 to x <= 5 then from 2 we would see positions > 5.\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 static long mod = (long) 1e9 + 7;\n  public static long base[] = { 4441, 7817 };\n\n  public static long[] get_hash(String s) {\n    long h[] = { 0, 0 };\n    for (int i = 0; i < s.length(); i++) {\n      h = add(multiply(base, h), s.charAt(i));\n    }\n    return h;\n  }\n\n  public static long[] multiply(long a[], long b[]) {\n    return new long[] { (a[0] * b[0]) % mod, (a[1] * b[1]) % mod };\n  }\n\n  public static long[] add(long a[], long b) {\n    return new long[] { (a[0] + b) % mod, (a[1] + b) % mod };\n  }\n\n  // create an object of hsh & initialise it in main method.\n  static class hsh {\n    int n;\n    String s;\n    long pre[][], pp[][];\n\n    void init(String S,HashSet<Index>set) {\n      s = S;\n      n = s.length();\n      pp = new long[n + 1][2];\n      pre = new long[n + 1][2];\n      pp[0] = new long[] { 1, 1 };\n      for (int i = 0; i < n; i++) {\n        pre[i + 1][0] = ((pre[i][0] * base[0]) % mod + s.charAt(i)) % mod;\n        pre[i + 1][1] = ((pre[i][1] * base[1]) % mod + s.charAt(i)) % mod;\n        set.add(new Index((pre[i+1][0]+mod)%mod,(pre[i+1][1]+mod)%mod));\n        if (i > 0) {\n          pp[i][0] = (pp[i - 1][0] * base[0]) % mod;\n          pp[i][1] = (pp[i - 1][1] * base[1]) % mod;\n        }\n      }\n    }\n\n    // returns hash of a substring (l,r) in O(1)\n    // l -> inclusive, r -> exclusive\n    long[] get(int s, int e) {\n      return new long[] { (pre[e][0] - (pre[s][0] * pp[e - s][0]) % mod + mod) % mod,\n          (pre[e][1] - (pre[s][1] * pp[e - s][1]) % mod + mod) % mod };\n    }\n  }\n\n    public static int dp[];\n\n  public static int fun( hsh ths, int i,int limit) {\n    if (i >= tlen) {\n      return 0;\n    }\n    if (dp[i] != -1) {\n      return dp[i];\n    }\n    int ans = (int)Math.pow(10,7);\n    int st = i;\n    // while (st < tlen) {\n      int low = 1, high = tlen - st;// length pr binary search\n      int yaha = -1;\n      while (low <= high) {\n        int mid = (low + high) / 2;\n        long tmp[]=ths.get(st,st+mid);\n        if(set.contains(new Index(tmp[0],tmp[1]))){\n          low = mid + 1;\n          yaha = mid;\n        } else {\n          high = mid - 1;\n        }\n      }\n      if (yaha == -1) {\n        return (int)Math.pow(10,7);\n      } else {\n        for (int k = limit; k <= yaha; k++) {\n          ans = Math.min(ans, 1 + fun(  ths,  i + k,Math.max(yaha-k,1)));\n        }\n      }\n\n    // }\n    return dp[i] = ans;\n  }\n  public static HashSet<Index> set;\n  public static int tlen;\n  public static int minValidStrings(String[] words, String target) {\n    int n = words.length;\n    set=new HashSet<>();\n    for (int i = 0; i < n; i++) {\n      hsh hs = new hsh();\n      hs.init(words[i],set);\n    }\n    HashSet<Index>dontuse=new HashSet<>();\n    hsh ths = new hsh();\n    ths.init(target,dontuse);\n    tlen = target.length();\n    dp = new int[tlen + 1];\n    Arrays.fill(dp, -1);\n    int aa1=fun(  ths,  0,1);\n    if(aa1==(int)Math.pow(10,7)){\n        aa1=-1;\n    }\n    return aa1;\n  }\n\n    // ----------------\n    public static class Index {\n\n        private long x;\n        private long y;\n\n        public Index(long x, long y) {\n            this.x = x;\n            this.y = y;\n        }\n\n        @Override\n        public int hashCode() {\n            return (int)(this.x ^ this.y);\n        }\n\n        @Override\n        public boolean equals(Object obj) {\n            if (this == obj)\n                return true;\n            if (obj == null)\n                return false;\n            if (getClass() != obj.getClass())\n                return false;\n            Index other = (Index) obj;\n            if (x != other.x)\n                return false;\n            if (y != other.y)\n                return false;\n            return true;\n        }\n    }\n    // -------------------------\n\n}\n```
['Java']