BFE.devでのAI解答例 - JavaScript コーディング問題
111. 回文のサブストリングを数える

解法1: ブルートフォース

まず最も単純な方法は、すべてのsubstringを列挙し、それが回文であるかどうかをチェックすることです。これにより、回文substringの数を数えることができます。すべてのsubstringを列挙するには、2つのforループを使用します。

/**
 * @param {string} s
 * @return {number}
 */
function countSubstrings(s) {
  let count = 0;

  // すべてのsubstringを列挙する
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      // substringを取得する
      let substring = s.substring(i, j + 1);
      // 回文であるかどうかをチェックする
      if (isPalindromic(substring)) {
        count++;
      }
    }
  }

  return count;
}

/**
 * 文字列が回文であるかどうかをチェックする
 * @param {string} s
 * @return {boolean}
 */
function isPalindromic(s) {
  for (let i = 0; i < Math.floor(s.length / 2); i++) {
    if (s[i] !== s[s.length - i - 1]) {
      return false;
    }
  }
  return true;
}

この解決策の時間複雑度はO（n ^ 3）です（すべてのsubstringを列挙し、各substringを回文であるかどうかチェックするのにO（n）かかるため）。空間複雑度はO（1）です。

改善点: 回文であるかどうかを判断するための別の方法を見つけることができます。実際、「中心を延長する」というアプローチを使用して、回文のsubstringであるかどうかを線形時間で判断できます。

解法2: 中心を延長する

基本的なアイデアは、各センター（1文字または2文字）を選択し、センターから左および右に進み、回文かどうかをチェックすることです。もし回文であれば、回文substringの数をカウントアップします。

/**
 * @param {string} s
 * @return {number}
 */
function countSubstrings(s) {
  let count = 0;

  // すべてのセンターを列挙する
  for (let center = 0; center < 2 * s.length - 1; center++) {
    let left = Math.floor(center / 2);
    let right = left + center % 2;

    // 回文を検索する
    while (left >= 0 && right < s.length && s.charAt(left) === s.charAt(right)) {
      count++;
      left--;
      right++;
    }
  }

  return count;
}

この解決策の時間複雑度はO（n ^ 2）です（各センターについて、左および右に進むために、最大n回の操作を行う必要があるため）。空間複雑度はO（1）です。