My job is to find the largest repeating substring in a given string, which repeats to re-create the entire string. For example, if input="cdcdcdcd" then the longest pattern would be "cdcd". If no substring can meet this requirement, return -1. Apparently the best possible time for this is 0(n), but I don't know what that means nor whether my solution meets that.
def StringPeriod(str) (str.length/2).downto(1) do |l| slices = str.chars.each_slice(l).to_a return slices.join if slices.uniq.size == 1 end -1 end
Please let me know how this could be optimized or written more clearly. And if you don't mind, please give me an idea of how to find faster solutions in general.
EDIT: After some thought, I figured this might be faster, but I'm still not quite sure if I'm onto it. See below:
def StringPeriod(str) (str.size-1).downto(1) do |sub| if str.size%sub==0 substring,n = str[0...sub],2 until substring.size*n > str.size return substring if substring*n==str n+=1 end end end -1 end
My third attempt:
def StringPeriod(str) n,f=1,str.size while n<=str.size/2 && f >=1 n+=1 until str.size%n==0 f-=1 until str.size%f==0 return str[0...n] if str[0...n]*f == str n+=1 f-=1 end -1 end