[Ruby][アルゴリズム問題]回文の文字列

頭の体操と勉強にアルゴリズム系の問題を解いてみました。

【問題】

文字列sが与えられた場合、sで最も長い回文部分文字列を返します。

【例】

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

自分で考えてみた回答（うまく書けず長くなってしまいました）

難しいポイントは
"aabaa"のような１文字を真ん中に回文となる場合と
"aabbaa"のように、２文字を真ん中に回文となる場合があることでしょうか。

def longest(s)
  # 1文字〜３文字の場合
  return s if s.size <= 1
  if s.size <= 3 && s[0] == s[s.size - 1]
    return s
  elsif s.size <= 3 && (s[0] == s[1] || s[1] == s[s.size - 1])
    return s[0]
  end

  # ４文字以上の場合
  # 文字列を配列に変換する
  arr = s.split("")
  longest_values = []
  arr.each.with_index do |str, i|
    if str == arr[i+1] && longest_values.empty?
      # ２文字の回文
      longest_values = (str*2).chars
    end
    if i > 0 && i != arr.size
      # 配列のi番目を真ん中の値として、左右対象となっているかを比べる場合
      left = arr[0..i-1]
      right = arr[i+1..arr.size-1]

      # 配列のi番目とi+1番目を真ん中の値として、左右対象となっているかを比べる
      left_include_self = arr[0..i]

      values_1 = left_right_symmetry?(left, right, arr, i)
      values_2 = left_right_symmetry?(left_include_self, right, arr, i)

      values = []
      if values_1.size > values_2.size
        values = values_1
      else
        values = values_2
      end

      if !values.empty? && values.size > longest_values.size
        longest_values = values
      end
    end
  end
  return longest_values.join
end

def left_right_symmetry?(left, right, arr, index)
    # 配列の数を少ない方に合わせ、左側はreverseする
    min_number = [left.size, right.size].min
    left_arranged = left.last(min_number).reverse
    right_arranged = right.first(min_number)

    values = []
    # 左右を比較し、対象になっている値をvaluesに加えていく
    min_number.times do |n|
      if left_arranged[n] == right_arranged[n]
        if values.empty? && (left.size + right.size != arr.size)
          values.push(arr[index])
        end
        values.unshift(left_arranged[n])
        values.push(right_arranged[n])
      end
    end
    return values
end

上記のコードで下記のテストは通ったので大丈夫そうです。

  test_patterns = {
    'aabaa' => 'aabaa',
    'aaccbb' => 'aa',
    'aabbcbbaa' => 'aabbcbbaa',
    'abababa' => 'abababa',
    'ab' => 'a',
    'aa' => 'aa',
    'aabbaacd' => 'aabbaa'
  }

もっと良いコード、良い回答あるかな？と思い、chatGPTに聞いてみると…
こんな回答が返ってきました。

def longest_palindrome(s)
  # 特殊な文字列 "$#" を挿入して、偶数長の回文も扱えるようにする
  t = "$#" + s.chars.join("#") + "#"
  
  # tの各文字を中心とする最長回文の半径を格納する配列
  p = Array.new(t.length, 0)
  
  # 右端が最も右にある回文の中心と半径
  center, max_right = 0, 0
  
  # p[i]を求める
  (1...t.length).each do |i|
    # 右端が最も右にある回文がiを含む場合、p[i]の初期値を更新する
    if max_right > i
      mirror = 2 * center - i
      p[i] = [max_right - i, p[mirror]].min
    end
    
    # iを中心とする回文を左右に広げていく
    while t[i + p[i] + 1] == t[i - p[i] - 1]
      p[i] += 1
    end
    
    # iを中心とする回文の右端が最も右にある場合、centerとmax_rightを更新する
    if i + p[i] > max_right
      center = i
      max_right = i + p[i]
    end
  end
  
  # pの最大値とそのインデックスを求める
  max_len = p.max
  center_idx = p.index(max_len)
  
  # s上での最長回文部分文字列を求める
  start_idx = (center_idx - max_len) / 2
  end_idx = start_idx + max_len
  return s[start_idx...end_idx]
end

chatGPTが試したテストは下記

puts longest_palindrome("babad")  # => "bab"
puts longest_palindrome("cbbd")   # => "bb"
puts longest_palindrome("a")      # => "a"
puts longest_palindrome("ac")     # => "a"

chatGPTの考え方おもしろいですね。
文字列の間に"#"などの文字を入れると、たしかに１文字中心での回文と２文字中心での回答どちらも一気に調べられそうです。
（ふと#が含まれている文字列は大丈夫なのかな？と思ったのですが問題なく返ってきました。すごい）

chatGPTに自分のコードを添削してもらってそちらを参考にしてみるのも勉強になります（が、バグっちゃうことあるので注意です）