1
\$\begingroup\$

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[0].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
\$\endgroup\$
  • \$\begingroup\$ O(n) is pronounced as Big O n basically Big O is used to calculate the worst case and best case scenario for the program in terms of time. I think the complexity for your program is O(n^2) as there are one level of check and one loop. \$\endgroup\$ – Smit Feb 26 '17 at 15:58
  • \$\begingroup\$ Always deduce the reuse of forloop by either reducing its iterations or by changing it to other forms! sometimes just some statements can solve the problem. \$\endgroup\$ – Smit Feb 26 '17 at 16:01
  • \$\begingroup\$ One way I can think of to shorten the time would be to only try slicing the string by even numbers if the string size is even, and by odd numbers if the size is odd. Other than that, I'm not sure. The go-to means of speeding things up, from what I've read, is to use a hash. But I'm not too comfortable with hashes yet. \$\endgroup\$ – Matthew Farabaugh Feb 26 '17 at 21:44
  • \$\begingroup\$ I had another idea. Please see my edit in the question \$\endgroup\$ – Matthew Farabaugh Feb 26 '17 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.