Submission #67625528

---

Source Code Expand

const fs = require("fs");

/**
 * 最長回文部分列の長さを返す関数
 * @param {string} S - 対象の文字列（英小文字）
 * @returns {number} - 最長の回文部分列の長さ
 */
function longestPalindromicSubsequence(S) {
    const N = S.length;
    const dp = Array.from({ length: N }, () => Array(N).fill(0));

    // 1文字は必ず回文
    for (let i = 0; i < N; i++) {
        dp[i][i] = 1;
    }

    // 長さ2以上の部分列に対するDP
    for (let len = 2; len <= N; len++) {
        for (let i = 0; i <= N - len; i++) {
            const j = i + len - 1;
            if (S[i] === S[j]) {
                dp[i][j] = (len === 2) ? 2 : dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][N - 1];
}

// 入力読み取り
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");
const N = Number(input[0]);
const S = input[1];

// 出力
console.log(longestPalindromicSubsequence(S));

Submission Info

Judge Result