# Here your code ! s = gets.chomp n = s.size dp = (n+1).times.map { Array.new(n+1) } dp[0][0] = [""] (1..n).each do |i| (0..i).each do |j| k = i - j a = [] a.concat(dp[j][k-1].map{|v| v + s[n - k] }) if k > 0 a.concat(dp[j-1][k].map{|v| v + s[j - 1] }) if j > 0 a.uniq! dp[j][k] ||= a end end r = [] (0..n).each do |i| r << dp[i][n-i] end puts r.flatten.uniq.size