HackerRank challenge - index palindrome

Question

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

Answer 1

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.

Answer 2

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