The Next Palindrome: Is my code efficient? I was trying to solve the Next Palindrome problem listed in SPOJ in Ruby language. Please find the problem statement here. Though i came up with the below solution, i could not get the execution time below 1.4s even after tweaking this code numerous times. Where can this code be optimized in terms of memory and execution time or is there a better approach than the solution i came up with?

def next_palindrome 
  number = gets.chomp
  len = number.length
  if len == 1
    return "11\n" if number == "9"
    return number.next!&lt;&lt;"\n" 
  end
  if len.even?
    f = len/2   
    return number[0..f-1]&lt;&lt;number[0..f-1].reverse&lt;&lt;"\n" if number[0..f-1]&gt;number[f..-1]
    number = number[0..f-1].next!
    return number&lt;&lt;number[0..f-1].reverse&lt;&lt;"\n"
  else
    f = (len-1)/2-1         
    return number[0..f+1]&lt;&lt;number[0..f].reverse&lt;&lt;"\n" if number[0..f]&gt;number[f+2..-1] 
    number = number[0..f+1].next!       
    return number&lt;&lt;number[0..f].reverse&lt;&lt;"\n"
  end
end

def input
  gets.chomp.to_i.times {print next_palindrome}      
end

input
Cache cache cache! :) All those substrings you take should be stored in variables, rather than using the expensive substring methods. Furthermore, comparing strings can also be expensive. When you store the substring in a variable, you could parse the integer and keep it for comparisons later.

Advanced:

Since you never need to look at the last half number (if it's a palindrome it must be the reverse of the first digits), you can just store two variables: big_half and small_half. for even-digit numbers, they will be equal, but for odd-digit numbers big_half will have the middle digit. This makes creating a that is adjacent to the number (either just smaller or just larger) as simple as big_half + small_half.reverse. If a test shows it's the smaller one, increment big_half and generate a new small_half from it, then add together as above.