[Kotlin] Dynamic Programming Approach for Repeated Substring
Intuition\nWe can approach this problem by simulating the process of forming str2 from str1 and keeping track of the counts of repetitions needed for each posit
# Intuition\nWe can approach this problem by simulating the process of forming `str2` from `str1` and keeping track of the counts of repetitions needed for each position in the repeated string `s1`. By efficiently tracking repetitions and identifying patterns, we can determine the maximum number of times `str2` can be obtained from `str1`.\n\n# Approach\n1. Initialize two hashmaps, `kToRepeatCount` and `nextIndexToK`, to store the count of repetitions needed for each position in the repeated string `s1` and the next index associated with each key `j`, respectively.\n2. Initialize variables `j` and `repeatCount` to track the current position in `s2` and the count of repetitions, respectively.\n3. Iterate through each repetition of `s1` up to `n1`.\n4. For each repetition, simulate the process of forming `s2` by comparing characters of `s1` and `s2` and updating `j` and `repeatCount` accordingly.\n5. If we encounter a repeating pattern, calculate the number of occurrences of the pattern and adjust the count accordingly.\n6. Return the maximum repetition count for `str2`.\n\n# Complexity\n- Time complexity: O(`s1` * n1), where `s1` is the length of s1. We iterate through each character of s1 for each repetition of n1.\n- Space complexity: O(n1). We store the count of repetitions and next index for each repetition of s1.\n\n# Code\n```\nclass Solution {\n    fun getMaxRepetitions(s1: String, n1: Int, s2: String, n2: Int): Int {\n        val kToRepeatCount = HashMap<Int, Int>()\n        val nextIndexToK = HashMap<Int, Int>()\n        kToRepeatCount[0] = 0\n        nextIndexToK[0] = 0\n        var j = 0\n        var repeatCount = 0\n        for (k in 1..n1) {\n            for (i in s1.indices) {\n                if (s1[i] == s2[j]) {\n                    j++\n                    if (j == s2.length) {\n                        j = 0\n                        repeatCount++\n                    }\n                }\n            }\n            if (nextIndexToK.containsKey(j)) {\n                val start = nextIndexToK[j]!!\n                val prefixCount = kToRepeatCount[start]!!\n                val patternCount = (n1 - start) / (k - start) * (repeatCount - prefixCount)\n                val suffixCount = kToRepeatCount[start + (n1 - start) % (k - start)]!! - prefixCount\n                return (prefixCount + patternCount + suffixCount) / n2\n            }\n            kToRepeatCount[k] = repeatCount\n            nextIndexToK[j] = k\n        }\n        return kToRepeatCount[n1]!! / n2\n    }\n}\n\n```
['Dynamic Programming', 'Kotlin']