/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function(s) {
  let [isPar,wi]=isP(s)
  if(isPar)return s
  let res='',mid
  wi=s.indexOf(s[wi])
  let nxtID=s.lastIndexOf(s[wi])
  while(true){
    mid=Math.floor((nxtID+wi) / 2)
    if((nxtID+wi) % 2===1){
      if(check(mid,mid+1,''))return res
    }else{
      if(check(mid-1,mid+1,s[mid]))return res
    }
    nxtID=s.lastIndexOf(s[wi],nxtID-1)
    if(nxtID===-1){
      let str=s.substring(wi),
          reverseS=str.split('').reverse().join('')
      return reverseS+shortestPalindrome(s.substring(0,wi))+str
    }
  }
  function isP(str){
    for(let i=0;i<str.length/2;i++){
      if(str[i]!==str[str.length-1-i])return [false,i]
    }
    return [true,null]
  }
  function check(l,r,str){
    while(r<s.length){
      let left,right=s[r]
      if(l<0)left=right
      else left=s[l]
      if(left!==right)return false
      str=left+str+right
      l--;
      r++
    }
    res=str
    return true
  }
};