构建最小字典序

题目

给定长度为N的字符串S（只包含大写英文字母），要构造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下列任意操作。

从S的头部删除一个字符，加到T的尾部 ；

从S的尾部删除一个字符，加到T的尾部。

目标是要构造字典序尽可能小的字符串T

字典序小：按照字母顺序，或者数字小大顺序，由小到大的形成序列

输入：

ACDBCB

输出

ABCBCD

实现

function change(str){
  let rs = ''
  let i = 0, j = str.length - 1
  while (i < j) {
    const head = str[i]
    const tail = str[j]
    if(head>tail){
      rs+=tail
      j--
    } else if (head < tail){
      rs+=head
      i++
    }else{
      let a = i+1,b=j-1
      while (a<=b){
        const head = str[a]
        const tail = str[b]
        if(head===tail){
          if(a===b){
            rs += str[i]
            i++
            break
          }else{
            a++
            b--
          }
        }else if(head>tail){
          rs += str[j]
          j--
          break
        }else{
          rs += str[i]
          i++
          break
        }
      }
    }
  }

  rs += str[i]

  return rs
}

console.log(change('ACACBA'))

解析

很多人都说这里要用贪心算法，但我觉得这里使用双指针更合适吧