在一个字符串上做操作：将连续重复字符消除。允许反复迭代操作。问：设计一个算法，通过合理安排消除次序，得到一个长度最短的结果串（结果可能不唯一，找到一个即可）。
如：
abbccd -> ad
abbcbbabbcbb -> acac
abcddcbe -> ae
abbbbccccbd -> ad
abccbbd -> ad
abbccaabbc -> a / c

求指教这个问题有什么好的解法不？

想到的一个方法是对重复子串作标记，然后“传染标记”，比如
    原始串：   abbbbccccbd
    压缩：     abcbd
    标记向量： 01100
    从0位开始，向后检测遇到的1，如果1和自身字符相同，或者第一个0和自身字符相同，配对都标记1
    第一轮：   01110（1位向后找第一个0（3位），和自身相同，都染为1，其中1位已经是1了）
    第二轮：   结束
    还原：     ad（把依然为0的输出）

但是这个方法对最后一个case无效：
    压缩：   abcabc
    标记：   011110
    第一轮： 111110（0位的a找到了后面标记为1的a）
    第二轮： 111111（2位的c找到了后面第一个标记0的是c）

一定保证正确的方法显然是穷举，对所有重复子串选择消或暂时不消，在生成的字符串空间中搜索，但是复杂度太高了。。。
--
FROM 123.58.117.*

栈不行，abbbcccbd，栈等于贪心，把bbb贪完了，后面的b消不掉了


【 在 tt2018 (tt2018) 的大作中提到: 】
: 用栈结构，入栈时检查一下
--
FROM 123.58.117.*

【 在 CKevin 的大作中提到: 】
: 栈不行，abbbcccbd，栈等于贪心，把bbb贪完了，后面的b消不掉了
:
:

abbccd
  a: [[0,0]] // 位置相同, 表示单字符, 留下
  b: [[1,2]] // 位置不同, 直接跳过
  c: [[3,4]] // 位置不同, 直接跳过
  d: [[5,5]] // 位置相同, 表示单字符, 留下
  => 倒着遍历 =>  da -> ad

abbcbbabbcbb
  a: [[0,0], [6,6]]
  b: [[1,2], [4,5], [7,8], [10,11]]
  c: [[3,3], [9,9]]
  => 倒着遍历 => b[10,11](跳过), 位置到 9(c) => c[9, 9](留下) => .....
  => c(9)/a(6)/c(3)/a(0) => acac
  
abcddcbe
  a: [[0, 0]]
  b: [[1,1], [1,6]]
  c: [[2,2], [2,5]]
  d: [[3,4]]
  e: [[7,7]]
  => e[7]/a[0] => ae
abbbbccccbd
  a: [[0,0]]
  b: [[1,9]]
  c: [[5,8]]
  d: [[10, 10]]
  => d[10]/a[0] => ad
abccbbd
  a: [[0,0]]
  b: [[1,5]]
  c: [[2,3]]
  d: [[6,6]]
  => d[6]/a[0] => ad
abbccaabbc
  a: [[0,6]]
  b: [[1,2], [7,8]]
  c: [[3,4], [9,9]]
  => c[9] => c
abcabc
  a: [[0,0], [3,3]]
  b: [[1,1], [4,4]]
  c: [[2,2], [5,5]]
  => c[5]/b[4]/a[3]/c[2]/b[1]/a[0] => abcabc
--
FROM 114.242.178.*

【 在 CKevin 的大作中提到: 】
: abcddcbe
:   a: [[0, 0]]
:   b: [[1,1], [1,6]]
: ...................


假设索引 index 的位置为 [start, end]

end：从 index 开始向后查找到与 str[index] 不相等为止，得到最大索引为 end
start: 从 index - 1 开始向前找，三种情况: 1) 遇到同str[index]相等字符为止(假设索引为j; 那么 start = j.start) 2）遇到单字符，修正为 start = index 3) 到 -1, 修正一下为 start = index。(ps: 可以优化下缓存. [[1,1],[1,6]] => [[1,6]])
--
FROM 114.242.178.*

相邻字节做减法，然后查找不为零的项。
【 在 CKevin 的大作中提到: 】
: 在一个字符串上做操作：将连续重复字符消除。允许反复迭代操作。问：设计一个算法，通过合理安排消除次序，得到一个长度最短的结果串（结果可能不唯一，找到一个即可）。
: 如：
: abbccd -> ad
: ...................
--
FROM 111.9.5.*