# Ruby Solution

• An related but slightly easier problem to the original one is finding the maximal # of `s2` that can be obtained from `S1`.

For example, assume `n2 = 3` and we can get 7 `s2` from `S1`, the final answer will be `7/3 = 2`

I start w/ a brute force algorithm by having two pointer `p1` and `p2`, which iterate through `S1` and `S2` respectively. This part is pretty straightforward.

The brute force algorithm has some room to improve when the `n1` is large. After some iterations, we may have enough information to calculate the answer w/o continuing.

For example, assume the following input

• s1 = "aaaaaab"
• n1 = 1,000,000
• s2 = "bc"

After the second iteration, we know we won't be able to find a match.

For those cases in which there are an answer, it's very like that there will be recurring pattern.

For example, assume the following input

• s1 = "ababc"
• n1 = 1,000,000
• s2 = "ba"
``````def get_max_repetitions(s1, n1, s2, n2)
count = get_max_repetitions_helper(s1, n1, s2)
count / n2
end

def get_max_repetitions_helper(s1, n1, s2)
p2 = 0
positions = []

(0...s1.size*n1).each do |p1|
# Give up when no char when can be matched w/ a full cyle
cycle = p1 / s1.size
return 0 if positions.size < cycle

c1, c2 = s1[p1 % s1.size], s2[p2 % s2.size]
if c1 == c2
positions[p2] = p1
# puts positions.each_with_index.map { |k,i| "(#{i}, #{k})" }.join(", ")

(p2-s2.size).step(0, -s2.size) do |i|
# Found pair (i, positions[i]) and (p2, positions[p2])
# where (p2-i) % s2.size == 0 and
#       (positions[p2] - positions[i]) % s1.size == 0
if (p1 - positions[i]) % s1.size == 0

parts = [
(positions.size-1),
(s1.size*n1-p1) / (positions[p2] - positions[i]) * (p2-i),
# How many extra s2 char can we match if
# if move p1 from [positions[i], positions[i+remain])
positions[i..-1].select do |k|
#   [ -------- remaining step for s1 -----------   ]
k <= (s1.size*n1-p1) % (positions[p2] - positions[i]) + positions[i] - 1
end.size
]

num_of_chars = parts.reduce(&:+)
return num_of_chars / s2.size
end
i -= s2.size
end

p2 += 1
end
end

positions.size / s2.size
end
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.