Count The Repetitions || Beats 100.00% of users with C++
\n\n\n# Intuition\n- The problem is to determine the maximum number of times a string s2 can be obtained from repeated concatenations of a string s1, given spec
![Screenshot 2024-05-28 105617.png](https://assets.leetcode.com/users/images/4a030d0e-a935-456f-84fb-09ea714b34ed_1716874011.988651.png)\n\n\n# Intuition\n- The problem is to determine the maximum number of times a string `s2` can be obtained from repeated concatenations of a string `s1`, given specific repetition counts `n1`and `n2` for s1 and `s2`, respectively.\n- The key challenge is to efficiently handle the potentially large repetition counts and avoid redundant calculations by identifying patterns.\n\n# Approach\n- **Initialization:**\n\n  - Calculate the lengths of `s1` and `s2`.\n  - Use arrays `repeatCount` and `nextIndex` to track the number of full sequences of `s2` formed and the position in `s2` after processing `k` repetitions of `s1`.\n  \n- **Simulate the Repetition of `s1`:**\n\n  - For each repetition of `s1`, iterate through its characters and try to match characters in `s2`.\n  - If a full sequence of `s2` is formed, increment the count and reset the position in `s2`.\n\n- **Cycle Detection:**\n\n  - Store the state (number of full sequences formed and the position in `s2`) after each repetition of `s1`.\n  - Check for cycles by comparing the current position in `s2` with previous positions. If a cycle is detected, calculate the number of full sequences of `s2` that can be formed using the cycle and the remaining repetitions of `s1`.\n\n- **Final Calculation:**\n\n  - If no cycle is detected, the result is directly obtained from the repeatCount array.\n  - If a cycle is detected, use the cycle information to compute the total number of full sequences of `s2`.\n\n# Complexity\n- **Time Complexity:** O(n1 * len1), where `n1` is the repetition count of `s1` and `len1` is the length of `s1`. This ensures we simulate each repetition of `s1` up to a maximum of `n1` times.\n- **Space Complexity:** O(n1), for storing the `repeatCount` and `nextIndex` arrays.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int getMaxRepetitions(string s1, int n1, string s2, int n2) {\n        int len1 = s1.size(), len2 = s2.size();\n        \n        // Step 1: Count how many full sequences of s2 can be formed from s1\n        vector<int> repeatCount(len2 + 1, 0), nextIndex(len2 + 1, 0);\n        int j = 0, count = 0;\n        \n        for (int k = 1; k <= n1; ++k) {\n            for (int i = 0; i < len1; ++i) {\n                if (s1[i] == s2[j]) {\n                    j++;\n                    if (j == len2) {\n                        j = 0;\n                        count++;\n                    }\n                }\n            }\n            repeatCount[k] = count;\n            nextIndex[k] = j;\n            \n            for (int start = 0; start < k; ++start) {\n                if (nextIndex[start] == j) {\n                    int interval = k - start;\n                    int repeatInterval = (n1 - start) / interval;\n                    int remaining = (n1 - start) % interval;\n                    \n                    return (repeatInterval * (count - repeatCount[start]) + repeatCount[start + remaining]) / n2;\n                }\n            }\n        }\n        \n        return repeatCount[n1] / n2;\n    }\n};\n\n```\n\n![UPVOTE FOR MORE.png](https://assets.leetcode.com/users/images/4a426dd4-6fea-4f0a-ac4e-a685e4ff9718_1716356905.3714855.png)
['String', 'Dynamic Programming', 'C++']