C++ | dfs + memo | recursion
Complexity

Time complexity: O(s1 * s2)


Space complexity: O(s1 * s2)

Code
# Complexity
- Time complexity: O(s1 * s2)

- Space complexity: O(s1 * s2)

# Code
```cpp []
class Solution {
public:
    /**
     * Find the maximum integer m such that [str2, m] can be obtained from str1
     * by removing some characters from str1.
     * 
     * @param s1 - First string that repeats n1 times to form str1
     * @param n1 - Number of times s1 repeats
     * @param s2 - Second string that repeats n2 times to form str2
     * @param n2 - Number of times s2 repeats in one 'unit' of [str2, m]
     * @return The maximum value of m
     */
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int s1Len = s1.size(), s2Len = s2.size();
        
        // If s1 or s2 is empty, or n1 is 0, we can't match anything
        if (s1Len == 0 || s2Len == 0 || n1 == 0) return 0;
        
        // This map stores previous states to detect cycles
        // Key: s2Idx (current position in s2)
        // Value: {s1Count, s2Count} - State when we were at this s2Idx before
        unordered_map<int, pair<int, int>> stateMap;
        
        // Memoization cache to avoid recomputing the same states
        // Key: "s1Count,s2Idx,s2Count" as a string
        // Value: maximum number of str2 units that can be obtained
        unordered_map<string, int> memo;
        
        // DFS function with memoization and cycle detection
        auto dfs = [&](auto&& self, int s1Count, int s2Idx, int s2Count) -> int {
            // Base case: if we've used all n1 copies of s1, return the result
            if (s1Count >= n1) return s2Count / n2;
            
            // Create a key for memoization
            string key = to_string(s1Count) + "," + to_string(s2Idx) + "," + to_string(s2Count);
            
            // Check if we've already computed this state
            if (memo.count(key)) return memo[key];
            
            // Check if we're in a cycle (same s2Idx as a previous state)
            if (stateMap.count(s2Idx)) {
                // Get the previous state with the same s2Idx
                auto [prevS1Count, prevS2Count] = stateMap[s2Idx];
                
                // Calculate the cycle length
                // cycleS1: number of s1 strings consumed in one cycle
                int cycleS1 = s1Count - prevS1Count;
                // cycleS2: number of s2 strings matched in one cycle
                int cycleS2 = s2Count - prevS2Count;
                // How many complete cycles we can skip
                int cycles = (n1 - s1Count) / cycleS1;
                
                // Example: If we found that every 3 copies of s1 produces 2 copies of s2,
                // and we have 1000 copies of s1 left, we can skip 333 cycles directly.
                
                // Skip these cycles by updating our counts
                s1Count += cycles * cycleS1;
                s2Count += cycles * cycleS2;
                
                // If we've used all n1 copies of s1 after skipping, return the result
                if (s1Count >= n1) return s2Count / n2;
            } else {
                // Record current state for future cycle detection
                stateMap[s2Idx] = {s1Count, s2Count};
            }
            
            // Process the next copy of s1
            int nextS2Idx = s2Idx;
            int nextS2Count = s2Count;
            
            // Process each character in one copy of s1
            for (int i = 0; i < s1Len; i++) {
                // If the current character in s1 matches the current character in s2
                if (s1[i] == s2[nextS2Idx]) {
                    nextS2Idx++;
                    
                    // If we've matched a complete copy of s2
                    if (nextS2Idx == s2Len) {
                        nextS2Idx = 0;  // Reset s2 index
                        nextS2Count++;  // Increment s2 count
                    }
                }
            }
            
            // Recursively process the next copy of s1
            int result = self(self, s1Count + 1, nextS2Idx, nextS2Count);
            
            // Store result in memoization cache
            memo[key] = result;
            return result;
        };
        
        // Start DFS with initial state: 0 copies of s1 used, at index 0 of s2, matched 0 copies of s2
        return dfs(dfs, 0, 0, 0);
    }
};
```
['Hash Table', 'String', 'Dynamic Programming', 'Depth-First Search', 'Recursion', 'Memoization', 'C++']