基于另一个字符串的字典中最小的字符串

Question

根据仅由> and <组成的输入字符串生成满足条件的字典式最小字符串的算法是什么？

例如

if input is "<<" then answer is "abc" // explanation "a<b<c"--> "a" is less than "b" and so does "c"
if input is "<>" then answer is "aba" // explanation "a<b>a"
if input is "<>><<" then answer is "acbabc" // explanation "a<c>b>a<b<c"

这个问题是在一次编码面试中提出的。约束：输入字符串的长度为2<=len(输入(<=10^6

任何解决此问题的提示也可以。

提前谢谢。

Answer 1

我可以想到一种贪婪的方法(未经测试(。

对于每一个<，我们只需要关心有多少个>连续地到右边+1(这里，+1是与<的前一个字符相关的当前字符(。

我们还初始化了一个current_char = a变量。

让我们以<>><<为例。计数如下：

<  >  >  <  <
3        1  1

现在，我们从数组的左向右移动，并根据current_char + count值分配值。现在，假设a + 3 = c也考虑当前字符。

对于连续的>个位置，我们只需将current_char减少1。

<  >  >  <  <
3        1  1
a c  b  a  b  c