transformable-string.rb

require 'set'
require 'pp'

def is_similar(s1, s2)

  # fast path
  if Set.new(s1.chars) != Set.new(s2.chars)
    return false
  elsif s1.size <= 2
    return true
  end

  s1.chars.each_with_index do |c, i|
    next if i == 0 || i == s1.size - 1
    s1_1 = s1.chars.slice(0, i)
    s1_2 = s1.chars.slice(i, 1e9)
    s2_1 = s2.chars.slice(0, s1.size - i)
    s2_2 = s2.chars.slice(s1.size - i, 1e9)

    # 左-右 右-左
    if Set.new(s1_1) == Set.new(s2_2) && is_similar(s1_1.join, s2_2.join) && is_similar(s2_1.join, s1_2.join)
      return true
    end

    # 左-左 右-右
    s1_1 = s1.chars.slice(0, i)
    s1_2 = s1.chars.slice(i, 1e9)
    s2_1 = s2.chars.slice(0, i)
    s2_2 = s2.chars.slice(i, 1e9)

    if Set.new(s1_1) == Set.new(s2_1) && is_similar(s1_1.join, s2_1.join) && is_similar(s2_2.join, s1_2.join)
      return true
    end
  end

  return false
end

p is_similar('ab', 'ba')
p is_similar('abc', 'bca')
p is_similar('bdc', 'bcd')
p is_similar('abcd', 'bdca')
p is_similar('abcd', 'bdac')