时间戳

首页 > 解决方案 > lexicographically smallest string based on another string

algorithm - lexicographically smallest string based on another string

问题描述

What is the algorithm to generate lexicographically smallest string satisfying condition based on input string consists of > and < only?

for example

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"

This question was asked in one of coding interview. Constraint: length of input string is 2<= len(input) <= 10^6

Any hint to solve this question will also be fine.

Thanks in advance.

标签： algorithmdata-structures

解决方案

我可以想到一个贪婪的方法（未经测试）。

对于每一个<，我们只需要关心有多少>个连续向右 + 1 （这里，+1 是当前字符相对于前一个字符的关系<）。

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

让我们举个<>><<例子。计数如下所示：

 <  >  >  <  <
 3        1  1

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

对于连续的>地方，我们只是减少current_char1。

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

推荐阅读