Problem Statement

James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words in the letter into palindromes.

While modifying the letters of the word, he follows 2 rules:

(a) He always reduces the value of a letter, e.g. he changes 'd' to 'c', but he does not change 'c' to 'd'. (b) If he has to repeatedly reduce the value of a letter, he can do it until the letter becomes 'a'. Once a letter has been changed to 'a', it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations he carries out to convert a given string into a palindrome.

The challange can be found here.

Input Format

The first line contains an integer \$T\$, i.e., the number of test cases. The next \$T\$ lines will contain a string each.

Output Format

A single line containing the number of minimum operations corresponding to each test case.


  • \$1 ≤ T ≤ 10\$
  • \$1 ≤\$ length of string \$≤ 104\$

All characters are lower cased English alphabets.

Sample Input


Sample Output


Test Cases

  • For the first test case, abc → abb → aba.
  • For the second test case, abcba is a palindromic string.
  • For the third test case, abcd → abcc → abcb → abca = abca → abba.


T = gets.chomp.to_i
result = []
def difference x,y
  (x.ord - y.ord).abs  
T.times do
  string = gets.chomp
  i,j = 0, -1
  n = 0
  loop do
    n = n + difference(string[i], string[j])
    i += 1
    j -= 1
    break if string.length % 2 == 0 ? i == (string.length/2) : i + j == -1 && string[i] == string[j] && i == string.length/2
  result << n

puts result
  • 4
    \$\begingroup\$ I do not speak Ruby but I guess there is a way to write this in a more concise/beautiful way. As an example, here's what I wrote in Python : print sum((abs(ord(s[i]) - ord(s[-i-1]))) for i in range(len(s)/2)). Basically, you need to go through your list in both direction (and stop at the middle), summing the differences between the two values you are considering. \$\endgroup\$ – Josay Jun 26 '14 at 17:12
  • 1
    \$\begingroup\$ @Josay Yup, you got it. In Ruby it'd be puts (s.length/2).times.inject(0) {|n, i| n += (s[i].ord - s[-1-i].ord).abs} \$\endgroup\$ – Flambino Jun 26 '14 at 19:26

Josay pretty much gave the answer in the comments. That line of Python is even very close to Ruby's way of writing it.

Meanwhile, ckuhn203 made a good point about the break line being obtuse.

Go upvote those two! This is just to provide alternative code.

Basically, you can do this instead:

# get number of words (T) and repeat that number of times
gets.chomp.to_i.times do
  # get word and map it to its ascii  values
  chars = gets.chomp.chars.map(&:ord)
  # print the sum of the difference between chars from either end of the string
  puts (chars.count/2).times.inject(0) { |sum, i| sum += (chars[i] - chars[-1-i]).abs }

Or you can skip the map(&:ord), and get closer Josay's code by getting the difference as (chars[i].ord - chars[-1-i].ord).abs


There is almost always a better way to loop in Ruby than actually using a loop. Unfortunately, I don't know Ruby well enough to say what that better way is.

What I can say is that this line of code is a bit obtuse.

break if string.length % 2 == 0 ? i == (string.length/2) : i + j == -1 && string[i] == string[j] && i == string.length/2

While it does seem to be a very Ruby way to write something like this, it's not very readable. Ternaries stretching off the screen are not a good thing in my opinion. It's okay to use an If block there.


Others have already given you good advise about your code. I'd add that the problem is that it's too imperative (change, update, accumulate). That leads to verbose and non-declarative code. Instead, a functional approach using expressions and known abstractions usually leads to more compact, declarative code. I'd write:

nlines = $stdin.readline.to_i
$stdin.take(nlines).each do |line|
  numbers = line.strip.chars.map(&:ord)
  pairs = numbers.zip(numbers.reverse).take(numbers.size / 2)
  sum = pairs.map { |n1, n2| (n1 - n2).abs }.reduce(0, :+)

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.