Count The Repetitions

                                            
function getMaxRepetitions(s1: string, n1: number, s2: string, n2: number): number {
    const dp: number[][] = [];
    for (let a = 0; a <= s2.length; a++) {
        dp[a] = [];
        let next = a;
        let count = 0;
        for (let b = 0; b < s1.length; b++) {
            if (s1[b] === s2[next]) {
                next++;
                if (next === s2.length) {
                    next = 0;
                    count++;
                }
            }
        }
        dp[a] = [next, count];
    }

    let ans = 0;
    let j = 0;
    let count = 0;
    for (let i = 0; i < n1; i++) {
        count += dp[j][1];
        j = dp[j][0];
        ans = Math.max(ans, count);
    }

    return Math.floor(ans / n2);
};

                                            
class Solution {
    func getMaxRepetitions(_ s1: String, _ n1: Int, _ s2: String, _ n2: Int) -> Int {
        var s1Chars = Array(s1)
        var s2Chars = Array(s2)
        
        var count1 = 0
        var count2 = 0
        var index = 0
        
        while count1 < n1 {
            for ch in s1Chars {
                if ch == s2Chars[index] {
                    index += 1
                    if index == s2Chars.count {
                        index = 0
                        count2 += 1
                    }
                }
            }
            count1 += 1
        }
        
        return count2 / n2
    }
}

                                            
impl Solution {
    pub fn get_max_repetitions(s1: String, n1: i32, s2: String, n2: i32) -> i32 {
        if n1 == 0 || n2 == 0 {
            return 0;
        }
        
        let s1_chars: Vec<char> = s1.chars().collect();
        let s2_chars: Vec<char> = s2.chars().collect();
        
        let mut repeats = 0;
        let mut s2_index = 0;
        
        for _ in 0..n1 {
            for &c in &s1_chars {
                if c == s2_chars[s2_index] {
                    s2_index += 1;
                    if s2_index == s2_chars.len() {
                        repeats += 1;
                        s2_index = 0;
                    }
                }
            }
        }
        
        repeats / n2
    }
}

To solve this coding challenge, you need to determine the maximum integer \( m \) such that the string representation \(\text{str2}\) concatenated \( m \) times can be obtained from the string representation \(\text{str1}\) concatenated \( n1 \) times. This is aided by efficiently mapping how characters in \( s1 \) align to characters in \( s2 \).

Explanation

Problem Understanding :

Given two strings \( s1 \) and \( s2 \) and their respective repetition counts \( n1 \) and \( n2 \).
We need to calculate how many times we can form \( \text{str2} = s2 \) \( n2 \) times from \( \text{str1} = s1 \) \( n1 \) times.

Initial Approach :

Since directly constructing strings \( \text{str1} \) and \( \text{str2} \) is computationally infeasible due to high \( n1 \) and \( n2 \), we focus on simulating the transformations indirectly.
Use a Dynamic Programming (DP) approach where we map progressions of \( s2 \) within \( s1 \).

Steps :

Construct a DP table where \( dp[i] \) represents the state of alignment within \( s2 \) after processing each character of \( s1 \).
For each character in \( s1 \), update the count of complete repetitions of \( s2 \) whenever the end of \( s2 \) is reached.
Continue tracing how far we can go in \( s2 \) after each character of \( s1 \).

Algorithm :

Build a DP table
dp

where
dp[i]

gives the next position in \( s2 \) and the count of complete repetitions of \( s2 \) after starting from position \( i \) of \( s2 \).
Iterate over \( n1 \) repetitions updating the state of \( s2 \) and counting complete \( s2 \) repetitions.
Calculate the maximum count of complete repetitions of \( \text{str2} \) in \( \text{str1} \).

Detailed Steps in Pseudocode

Initialization :

Create a DP array to track how \( s2 \) can be traversed within \( s1 \).

                                            
# Initialize the DP table for s2's length.
dp = []

for each position_in_s2 from 0 to length_of_s2:
# Initialize the next position and count of complete s2's repetitions
next_position = position_in_s2
complete_s2_repetitions = 0
for each position_in_s1 in length_of_s1:
if s1[position_in_s1] matches s2[next_position]:
next_position += 1
if next_position equals length_of_s2:
next_position = 0
complete_s2_repetitions += 1
# Store the state in DP table
dp[position_in_s2] = [next_position, complete_s2_repetitions]

Processing \( n1 \) repetitions of \( s1 \) :

Traverse the DP table to compute how many \( s2 \) repetitions happen within \( n1 \) repetitions of \( s1 \).

                                            
current_position_s2 = 0
total_s2_repetitions = 0

for each repetition_in_n1 from 0 to n1 - 1:
# Update the total count by using the DP table
total_s2_repetitions += dp[current_position_s2][1]
current_position_s2 = dp[current_position_s2][0]

# Calculate the maximum m based on n2
maximum_m = total_s2_repetitions // n2

Return the Result :

Return the computed maximum m.

                                            
Return maximum_m

Summary

This approach ensures efficient calculation by leveraging DP to avoid reconstructing large strings, thus optimizing the solution to work within the constraints of the problem.

                                            
# Calculate the state transitions for s2 in s1
dp = []

for each i from 0 to length_of_s2:
    # Initialize next position and count
    current_next = i
    current_count = 0
    for each j in length_of_s1:
        if s1[j] == s2[current_next]:
            current_next += 1
            if current_next == length_of_s2:
                current_next = 0
                current_count += 1
    dp[i] = [current_next, current_count]

# Calculate the number of s2 repetitions within n1 repetitions of s1
current_index = 0
total_repetitions = 0

for each i from 0 to n1 - 1:
    total_repetitions += dp[current_index][1]
    current_index = dp[current_index][0]

# Determine maximum m based on n2
maximum_m = total_repetitions // n2

Return maximum_m