HackerRank challenge - index palindrome

I have a solution but it fails the performance for two tests. How can I speed it up?

def palindrome?(str)
str.reverse == str
end

def parse(str)
return -1 if palindrome?(str)

str.length.times do |i|
before = str[0...i]
after = str[i+1...str.length]
return i if palindrome?(before + after)
end
end

tests = gets.strip.to_i
tests.times do
str = gets.strip
puts parse(str)
end


I tried replacing my palindrome checker function but using benchmarking this seems to actually execute slower:

def palindrome?(str)
(str.length/2).times do |i|
return false if str[i] != str[-(i+1)]
end
true
end
enter code here


First of all, your palindrome function uses inefficient logic. Reversing a string takes N steps, where N is the length of the string. Comparing a string to its reverse takes some additional steps, though typically not that many for ordinary strings, near N / 2 steps for almost-palindromes, N steps for palindromes, but that's not a real concern.

The important thing is that you can check if a string is palindrome in N / 2 steps by comparing the ith character from start and end. The even more important thing is that you can use this logic to fond the index that breaks a palindrome, significantly speeding up your parse function.

As a final remark about good coding practices, your parse function does too many things, and it's also poorly named. It would be better to decompose this to multiple functions that each do one logical thing, and name them accordingly.

Ah. Found a soltn. So obvious in hindsight.

def palindrome?(str)
str.reverse == str
end

def parse(str)
return -1 if palindrome?(str)

(str.length/2).times do |i|

if str[i] != str[-(i+1)]
before = str[0...i]
after = str[i+1...str.length]
if palindrome?(before + after)
return i
end
before = str[0...-(i+1)]
after = str[(str.length-i)...str.length]
if palindrome?(before + after)
return str.length-i-1
end
end
end
end

tests = gets.strip.to_i
tests.times do
str = gets.strip
puts parse(str)
end