如何去除字符串中的重复字符并按最长出现顺序打印

Question

我一直在尝试解决这个程序，但我做不到。

x="abcaa" # sample input
x="bca" # sample output

我试过这个：

from collections import OrderedDict
def f(x):
    print ''.join(OrderedDict.fromkeys(x))
t=input()
for i in range(t):
    x=raw_input()
    f(x)

上面的代码给出的结果是：

x="abcaa" # Sample input
x="abc" # sample output

更多细节：

示例输入：

 abc
 aaadcea
 abcdaaae

示例输出：

abc
adce
bcdae

在第一个例子中，字符串是“abcaa”，这里‘a’在最后重复最多，所以它被放在最后，结果是“bca”。而在另一个例子“aaadcea”中，‘a’在开头重复最多，所以它被放在最前面，结果是“adce”。

Answer 1

这个解决方案看起来不太优雅，甚至有点丑，而且效率也不高，几乎可以肯定不是用Python的标准方式，但我觉得它能满足你的需求。

t = raw_input('Write your string here: ')

# Create a list initalized to 0 to store character counts
seen = dict()

# Make sure actually have a string
if len(t) < 1:
  print ""
else:
  prevChar = t[0]
  count = 0
  for char in t:
    if char == prevChar:
      count = count + 1
    else:
      # Check if the substring we just finished is the longest
      if count > seen.get(prevChar, 0):
        seen[prevChar] = count
      # Characters differ, restart
      count = 1
    prevChar = char

  # Append last character
  seen[prevChar] = count

  # Now let's build the string, appending the character when we find the longest version
  count = 0
  prevChar = t[0]
  finalString = ""
  for char in t:
    if char in finalString:
      # Make sure we don't append a char twice, append the first time we find the longest subsequence
      continue
    if char == prevChar:
      count = count + 1
    else:
      # Check if the substring we just finished is the longest
      if count == seen.get(prevChar, 0):
        finalString = finalString + prevChar
      # Characters differ, restart
      count = 1
    prevChar = char

  # Check the last character
  if count == seen[prevChar]:
    finalString= finalString + prevChar

  print finalString

Answer 2

这个 OrderedDict 对你没有帮助，因为你保持的顺序并不是你想要的。

如果我理解你的问题（我也不太确定我理解得对不对……）你想要的顺序是一个排序过的顺序，也就是说，按照字符出现的次数来排序，出现次数最多的字符应该排在最后。

所以，这意味着你需要以某种方式将每个字符和它的出现次数关联起来。你可以用一个显式的循环和 d.setdefault(char, 0) 这样的方式来实现，但如果你查看一下 collections 的文档，你会看到有一个叫 Counter 的东西，正好在 OrderedDict 的旁边，它是：

一个用于计数可哈希对象的字典子类

这正是你想要的：

>>> x = 'abcaa'
>>> collections.Counter(x)
Counter({'a': 3, 'b': 1, 'c': 1})

现在你只需要用一个 key 函数来排序：

>>> ''.join(sorted(c, key=c.__getitem__))
'bca'

如果你想要这个排序是稳定的，也就是说，出现次数相同的元素要按照它们第一次出现的顺序来显示，或者按照它们第一次达到那个次数的顺序来显示，那么你确实需要 OrderedDict。那么，如何同时获得 OrderedDict 和 Counter 的功能呢？文档中有一个 示例 可以告诉你怎么做。（其实你并不需要那么复杂；__repr__ 和 __reduce__ 对你的使用来说并不重要，所以你可以直接从 Counter 和 OrderedDict 继承，然后在主体部分用 pass。）

Answer 3

我来猜一下你想要的内容：

对于每个字符，你需要找到它出现次数最多的位置。

这意味着在处理每个字符时，你需要记录两个东西：到目前为止它出现次数最多的位置，以及出现的次数。同时，你还需要跟踪当前字符的连续出现情况。

在这种情况下，OrderedDict 是必要的，但仅仅有它还不够。你需要在找到字符时把它们添加到 OrderedDict 中，当你发现更长的连续字符时，要把它们移除再重新添加，并且你还需要在每个键的值中存储一个计数，而不仅仅是把 OrderedDict 当作一个 OrderedSet 来用。像这样：

d = collections.OrderedDict()
lastch, runlength = None, None
for ch in x:
    if ch == lastch:
        runlength += 1
    else:
        try:
            del d[lastch]
        except KeyError:
            pass
        if runlength:
            d[lastch] = runlength
        lastch, runlength = ch, 1
try:
    del d[lastch]
except KeyError:
    pass
if runlength:
    d[lastch] = runlength
x = ''.join(d)

---

你可能会注意到这里有点重复，而且说得有点啰嗦。你可以通过把问题分成两步来简化：首先把字符串压缩成连续的字符，然后只需跟踪每个字符的最大连续出现次数。得益于迭代器的神奇，这两步其实可以在一次处理里完成，第一步可以懒惰地进行。

另外，因为你还在使用 Python 2.7，所以没有 OrderedDict.move_to_end 这个功能，我们需要做一些繁琐的删除再添加的操作，但我们可以用 pop 来让这个过程更简洁。

所以：

d = collections.OrderedDict()
for key, group in itertools.groupby(x):
    runlength = len(list(group))
    if runlength > d.get(key, 0):
        d.pop(key, None)
        d[key] = runlength
x = ''.join(d)

---

另一种解决方法是使用普通的字典，存储每个字符的连续长度和位置，然后按位置排序结果。这样我们就不需要做移动到末尾的操作了，只需在更新值时更新位置：

d = {}
for i, (key, group) in enumerate(itertools.groupby(x)):
    runlength = len(list(group))
    if runlength > d.get(key, (None, 0))[1]:
        d[key] = (i, runlength)
x = ''.join(sorted(d, key=d.__getitem__))

不过，我不确定这个改进是否真的提高了可读性，所以我还是会选择上面提到的第二种版本。