Count The Repetitions || JAVA || EASY
Intuition\n Describe your first thoughts on how to solve this problem. \n\nTo solve this problem, we need to determine how many times we can form the string str
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nTo solve this problem, we need to determine how many times we can form the string str2 from str1. Given the constraints of the problem, we must *find an efficient way to simulate the formation of str2 from repeated sequences of s1*. One way to achieve this is by tracking how many times characters from s2 can be matched within the repeated sequences of s1. By recognizing patterns and cycles, we can significantly reduce the number of iterations required to find the solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nInitialize Counters and State Tracking:\n\nUse counters s1Count and s2Count to keep track of how many times we have iterated through s1 and fully matched s2, respectively.\nUse s2Index to track the current position in s2 that we are trying to match with characters from s1.\nUse a map (recall) to store the state (s2Index) and corresponding counts (s1Count, s2Count) to detect cycles.\nSimulate Matching:\n\nIterate through s1 and try to match characters with s2 using the s2Index.\nIf a character from s1 matches the current character from s2 (pointed by s2Index), move s2Index to the next character.\nIf s2Index reaches the end of s2, increment s2Count and reset s2Index to zero.\nCycle Detection:\n\nAfter processing each repetition of s1, check if the current state (s2Index) has been seen before using the map.\nIf a state is repeated, a cycle is detected. Calculate the number of full cycles that can fit into the remaining repetitions of s1 and adjust s1Count and s2Count accordingly.\nIf the state is new, store the current state in the map.\nCalculate Result:\n\nFinally, compute the number of complete [s2, n2] repetitions that can be formed from the total s2Count.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nTime complexity: **O(n1\u22C5s1.length())**\nIn the worst case, we might need to iterate through the entire string s1 up to n1 times. Each iteration involves traversing the length of s1, leading to the time complexity.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nSpace complexity: **O(s2.length())**\nThe space complexity is determined by the size of the map recall, which can store up to s2.length() unique states (s2Index values).\n\n# Code\n```\nimport java.util.HashMap;\nimport java.util.Map;\nclass Solution {\n    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {\n        if (n1 == 0) return 0;\n        int s1Count = 0, s2Count = 0, s2Index = 0;\n        Map<Integer, int[]> recall = new HashMap<>();\n        while (s1Count < n1) {\n            for (int i = 0; i < s1.length(); i++) {\n                if (s1.charAt(i) == s2.charAt(s2Index)) {\n                    s2Index++;\n                    if (s2Index == s2.length()) {\n                        s2Count++;\n                        s2Index = 0;\n                    }\n                }\n            }\n            s1Count++;\n            if (recall.containsKey(s2Index)) {\n                int[] previous = recall.get(s2Index);\n                int prevS1Count = previous[0];\n                int prevS2Count = previous[1];\n                \n                int cycleLength = s1Count - prevS1Count;\n                int cycleS2Count = s2Count - prevS2Count;\n                \n                int remainingCycles = (n1 - s1Count) / cycleLength;\n                \n                s1Count += remainingCycles * cycleLength;\n                s2Count += remainingCycles * cycleS2Count;\n            } else {\n                recall.put(s2Index, new int[]{s1Count, s2Count});\n            }\n        }\n        return s2Count / n2;\n    }\n}\n```
['Java']