Accepted 8ms Java solution with explanation
IDEA: \nImagine s1 and s2 repeat inifinite times as below (for example s1 = "abcd" and \ns2 = "ab") \nabcdabcdabcd... \nababab... \nsay  are pairs of pointers t
**IDEA:** \nImagine s1 and s2 repeat inifinite times as below (for example s1 = "abcd" and \ns2 = "ab") \nabcdabcdabcd... \nababab... \nsay <i, j> are pairs of pointers to s1 and s2 in greedy matched characters, \nin above example will be \n<0, 0>, <1, 1>, <4, 2>, <5, 3>, <8, 4>, <9, 5>... \nIn a brute force solution we can keep increasing i and j until i exceeds s1 x n1.\n\nSay the lengths of s1 and s2 are m1 and m2. It's easy to prove that: \nIf there are two pairs <i1, j1>, <i2, j2> satisfying: \n(i2 - i1) % m1 == 0 && (j2 - j1) % m2 == 0, \nlet d1 = i2 - i1 and d2 = j2 - j1, \nthen for all positive integer k, <i1 + d1 * k, j1 + d2 * k> will be pairs too.\n\nSo without brute force matching, my trick is to use above conclusion to push <i,\nj> quickly to near the end of the expanded string s1 x n1, after the first <i1,\nj1> and <i2, j2> pair is found. Here's the solution:\n\n```\npublic class Solution {\n\tpublic int getMaxRepetitions(String s1, int n1, String s2, int n2) {\n\t\tint m1 = s1.length();\n\t\tint m2 = s2.length();\n\t\tif (m1 == 0 || m2 == 0)\n\t\t\treturn 0;\n\t\tint i, j;\n\t\t// extra code to remove unnecessary characters in s1\n\t\tStringBuffer sb = new StringBuffer();\n\t\tboolean[] used = new boolean[26];\n\t\tint[] counts = new int[26]; // count of each character in s1\n\t\tfor (i = 0; i < m2; i++) {\n\t\t\tj = s2.charAt(i) - 'a';\n\t\t\tused[j] = true;\n\t\t}\n\t\tfor (i = 0; i < m1; i++) {\n\t\t\tj = s1.charAt(i) - 'a';\n\t\t\tif (used[j])\n\t\t\t\tsb.append(s1.charAt(i));\n\t\t\tcounts[j]++;\n\t\t}\n\t\tfor (i = 0; i < 26; i++) {\n\t\t\tif (used[i] && counts[i] == 0) // character in s2 not in s1\n\t\t\t\treturn 0;\n\t\t}\n\t\ts1 = sb.toString();\n\t\tm1 = s1.length();\n\n\t\t// extra code to reduce s1 and s2 if it contains repeating pattern\n\t\tfor (i = 1; i <= m1 / 2; i++) {\n\t\t\tif (m1 % i != 0)\n\t\t\t\tcontinue;\n\t\t\tif (repeatAtK(s1, i)) {\n\t\t\t\ts1 = s1.substring(0, i);\n\t\t\t\tn1 *= m1 / i;\n\t\t\t\tm1 = i;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\tfor (i = 1; i <= m2 / 2; i++) {\n\t\t\tif (m2 % i != 0)\n\t\t\t\tcontinue;\n\t\t\tif (repeatAtK(s2, i)) {\n\t\t\t\ts2 = s2.substring(0, i);\n\t\t\t\tn2 *= m2 / i;\n\t\t\t\tm2 = i;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\n\t\tint[][] ocs = new int[26][m1]; // occurrences of each character in s1\n\t\tArrays.fill(counts, 0);\n\t\tfor (i = 0; i < m1; i++) {\n\t\t\tj = s1.charAt(i) - 'a';\n\t\t\tocs[j][counts[j]] = i;\n\t\t\tcounts[j]++;\n\t\t}\n\t\t\n\t\t// simple case\n\t\tif (m2 == 1) {\n\t\t\tj = s2.charAt(0) - 'a';\n\t\t\treturn counts[j]*n1/n2;\n\t\t}\n\n\t\treturn getMaxRepetitionsProcessed(counts, ocs, n1, s2.toCharArray(), n2);\n\t}\n\n\tpublic int getMaxRepetitionsProcessed(int[] counts, int[][] ocs, int n1, char[] ca2, int n2) {\n\t\tint m1 = ocs[0].length;\n\t\tint m2 = ca2.length;\n\t\t// <i, j> pairs in slot mod m1/m2\n\t\tint[][][] r = new int[m1][m2][2];\n\t\t// pos[c][0] is the current index of character c in i, \n\t\t// pos[c][1] is which occurrence in s1\n\t\tint[][] pos = new int[26][2]; \n\t\tint i, j, k, r1 = 0, r2 = 0;\n\t\tboolean found = false;\n\t\tfor (i = 0; i < 26; i++) {\n\t\t\tpos[i][0] = ocs[i][0];\n\t\t}\n\t\tfor (i = 0; i < m1; i++) {\n\t\t\tfor (j = 0; j < m2; j++) {\n\t\t\t\tr[i][j][0] = -1;\n\t\t\t}\n\t\t}\n\t\tfor (i = 0, j = 0; i < m1 * n1; i++, j++) {\n\t\t\tk = ca2[j % m2] - 'a';\n\t\t\t// move pos[k] to a position equal or after i by iterating k's occurrences\n\t\t\twhile (pos[k][0] < i) {\n\t\t\t\tpos[k][1]++;\n\t\t\t\tif (pos[k][1] < counts[k]) {\n\t\t\t\t\tpos[k][0] += ocs[k][pos[k][1]] - ocs[k][pos[k][1] - 1];\n\t\t\t\t} else {\n\t\t\t\t\tpos[k][1] = 0;\n\t\t\t\t\tpos[k][0] += ocs[k][0] + m1 - ocs[k][counts[k] - 1];\n\t\t\t\t}\n\t\t\t}\n\t\t\ti = pos[k][0];\n\t\t\tif (i >= m1 * n1) {\n\t\t\t\treturn j / m2 / n2;\n\t\t\t}\n\t\t\tr1 = i % m1;\n\t\t\tr2 = j % m2;\n\t\t\tif (!found && r[r1][r2][0] < 0) {\n\t\t\t\tr[r1][r2][0] = i;\n\t\t\t\tr[r1][r2][1] = j;\n\t\t\t} else if (!found) { // push by mod trick here\n\t\t\t\tint d1 = i - r[r1][r2][0];\n\t\t\t\tint d2 = j - r[r1][r2][1];\n\t\t\t\tk = (m1 * n1 - i) / d1;\n\t\t\t\ti += k * d1;\n\t\t\t\tj += k * d2;\n\t\t\t\tfor (r1 = 0; r1 < 26; r1++) { // update all pos[c] the same way as i\n\t\t\t\t\tpos[r1][0] += k * d1;\n\t\t\t\t}\n\t\t\t\tfound = true;\n\t\t\t}\n\t\t}\n\t\treturn j / m2 / n2;\n\t}\n\n\tpublic boolean repeatAtK(String s, int k) { // check if s is repeated every k characters\n\t\tint m = s.length();\n\t\tint x = m / k;\n\t\tfor (int i = 0; i < k; i++) {\n\t\t\tfor (int j = 0; j < x; j++) {\n\t\t\t\tif (s.charAt(i) != s.charAt(j * k + i))\n\t\t\t\t\treturn false;\n\t\t\t}\n\t\t}\n\t\treturn true;\n\t}\n}\n```\n\nRegarding the time complexity, the for loop should be less than 2 * m1 * m2\ntimes according to pigeonhole theorem, and the while loop inside should be less\nthant m1 (actually can be amortized to d1/d2), so the overall time complexity\nshould be less than O(m1 * m1 * m2). I believe in reality it should be much less. \n\nUgly coding because I'm not good at it, just want to share this idea to see if \nit makes sense. Any improvement is most welcome.
[]