Ruby Solution


  • 0

    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
    

Log in to reply
 

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