💥💥 Runtime beats 99.21%, Memory beats 98.43%
Intuition\nThe problem asks how many times we can fully form the string s2 (repeated n2 times) from the string s1 (repeated n1 times). We need to efficiently co
# Intuition\nThe problem asks how many times we can fully form the string s2 (repeated n2 times) from the string s1 (repeated n1 times). We need to efficiently count how often s2 fits into s1 as we repeat s1 multiple times. The key is to look for patterns to avoid unnecessary work.\n\n# Approach\nMatch s2 in s1: Start matching s2 within each repetition of s1. Track how many times you can fully form s2.\n\nDetect Patterns: As you match, keep track of your progress. If you notice the same progress repeating, you\'ve found a pattern. Use this pattern to jump ahead and skip redundant work.\n\nFinal Count: Once all repetitions of s1 are processed, calculate how many complete s2 strings you were able to form and divide by n2 to get the result.\n\n# Complexity\n- Time complexity:\nO(s1.length * s2.length): In the worst case, we might have to iterate through every character of s1 for each character of s2 until we detect a loop or exhaust the repetitions.\n\n- Space complexity:\nO(s2.length): The space is primarily used by the dictionary that tracks the states (index in s2). This dictionary has a size proportional to the length of s2.\n\n# Code\n```python3 []\nclass Solution:\n    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:\n        # Early exit if s1 is too small to contain s2\n        if n1 == 0:\n            return 0\n        \n        s1_count, s2_count, index = 0, 0, 0\n        recall = {}\n\n        # Process s1 n1 times\n        while s1_count < n1:\n            s1_count += 1\n            for char in s1:\n                if char == s2[index]:\n                    index += 1\n                if index == len(s2):\n                    s2_count += 1\n                    index = 0\n            \n            # Detect and handle loops\n            if index in recall:\n                prev_s1_count, prev_s2_count = recall[index]\n                loop_s1_count = s1_count - prev_s1_count\n                loop_s2_count = s2_count - prev_s2_count\n                \n                # Calculate how many times the loop can repeat\n                remaining_loops = (n1 - s1_count) // loop_s1_count\n                s1_count += remaining_loops * loop_s1_count\n                s2_count += remaining_loops * loop_s2_count\n\n            recall[index] = (s1_count, s2_count)\n        \n        return s2_count // n2\n\n```
['Python3']