NC17.最长回文子串

题目描述[https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=188&rp=1&ru=%2Fta%2Fjob-code-high-week&qru=%2Fta%2Fjob-code-high-week&difficulty=&judgeStatus=&tags=&title=NC17&sourceUrl=&gioEnter=menu]

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

TIP

标签：字符串、动态规划

关联企业：腾讯、华为、美团、京东

关联职位：前端、研发、测试、算法

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param A string字符串
 * @param n int整型
 * @return int整型
 */
export function getLongestPalindrome(A: string, n: number): number {
  if (A === null || A === undefined) {
    return;
  }
  // 题目中的数据范围是 1 ~ 1000 所以这个判断是有必要的
  if (A.length < 2) {
    return A.length;
  }

  let maxlen = 1;
  // 开始位置索引
  let begin = 0;

  for (let i = 0; i < A.length; i++) {
    let oddlen = helper(A, i, i);
    let evenlen = helper(A, i, i + 1);
    let curlen = Math.max(oddlen, evenlen);
    if (curlen > maxlen) {
      maxlen = curlen;
      begin = i - Math.floor((maxlen - 1) / 2);
    }
  }
  
  return A.substring(begin, begin + maxlen).length;
}

function helper(A, left, right) {
  while (left >= 0 && right < A.length) {
    if (A.charAt(left) === A.charAt(right)) {
      left--;
      right++;
    } else {
      break;
    }
  }
  return right - left - 1;
}