1

我需要一种算法来通过删除字符（不重新排列）从字符串中找到最大的唯一（无重复字符）子字符串。

如果满足这两个条件，则字符串 A 大于字符串 B。

1. Has more characters than String B
   Or
2. Is lexicographically greater than String B if equal length

例如，如果输入字符串是dedede，则可能的唯一组合是de、ed、d和e。
在这些组合中，最大的一个因此是ed，因为它比d和e具有更多的字符，并且在字典上大于de。

该算法必须比生成所有可能的唯一字符串并对其进行排序以找到最大的字符串更有效。

注意：这不是家庭作业。

4

2 回答 2

2

这个怎么样

string getLargest(string s) 
{
        int largerest_char_pos=0;
        string result="";
        if(s.length() == 1) return s;
        for(int i=0;i<s.length();)
        {
            p=i;
            for(int j=i+1;j<s.length();j++)
            {
                if(s[largerest_char_pos]< s[j]) largerest_char_pos =j;
            }
            res+=s[largerest_char_pos];
            i=largerest_char_pos+1;
        }
        return result;      
    }

这是代码片段，只是为您提供了字典上更大的字符串。如果您不想重复，您可以只跟踪已添加的字符。

于 2013-12-07T18:29:39.497 回答
1

让我以我认为更清楚的方式陈述订购规则。

如果字符串 A 大于字符串 B

- A is longer than B
  OR
- A and B are the same length and A is lexicographically greater than B

如果我对规则的重述是正确的，那么我相信我有一个在 O(n^2) 时间和 O(n) 空间中运行的解决方案。我的解决方案是一种贪心算法，它基于以下观察：最长有效子序列中的字符数与输入字符串中的唯一字符数一样多。我是用 Go 写的，希望这些评论足以描述算法。

func findIt(str string) string {
  // exc keeps track of characters that we cannot use because they have
  // already been used in an earlier part of the subsequence
  exc := make(map[byte]bool)

  // ret is where we will store the characters of the final solution as we
  // find them
  var ret []byte

  for len(str) > 0 {
    // inc keeps track of unique characters as we scan from right to left so
    // that we don't take a character until we know that we can still make the
    // longest possible subsequence.
    inc := make(map[byte]bool, len(str))

    fmt.Printf("-%s\n", str)
    // best is the largest character we have found that can also get us the
    // longest possible subsequence.
    var best byte

    // best_pos is the lowest index that we were able to find best at, we
    // always want the lowest index so that we keep as many options open to us
    // later if we take this character.
    best_pos := -1

    // Scan through the input string from right to left
    for i := len(str) - 1; i >= 0; i-- {
      // Ignore characters we've already used
      if _, ok := exc[str[i]]; ok { continue }

      if _, ok := inc[str[i]]; !ok {
        // If we haven't seen this character already then it means that we can
        // make a longer subsequence by including it, so it must be our best
        // option so far
        inc[str[i]] = true
        best = str[i]
        best_pos = i
      } else {
        // If we've already seen this character it might still be our best
        // option if it is a lexicographically larger or equal to our current
        // best.  If it is equal we want it because it is at a lower index,
        // which keeps more options open in the future.
        if str[i] >= best {
          best = str[i]
          best_pos = i
        }
      }
    }


    if best_pos == -1 {
      // If we didn't find any valid characters on this pass then we are done
      break
    } else {
      // include our best character in our solution, and exclude it for
      // consideration in any future passes.
      ret = append(ret, best)
      exc[best] = true

      // run the same algorithm again on the substring that is to the right of
      // best_pos
      str = str[best_pos+1:]
    }
  }
  return string(ret)
}

我相当肯定你可以在 O(n) 时间内做到这一点，但我不确定我的解决方案，所以我发布了这个。

于 2012-04-08T22:55:38.803 回答