1

文字を削除する（再配置しない）ことにより、文字列から最大の一意の（重複する文字がない）部分文字列を見つけるアルゴリズムが必要です。

文字列Aは、これら2つの条件を満たす場合、文字列Bよりも大きくなります。

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

たとえば、入力文字列がdededeの場合、可能な一意の組み合わせはde、ed、d、およびeです。
したがって、これらの組み合わせのうち、最大のものは、dおよびeよりも文字数が多く、辞書式順序でdeよりも大きいため、 edになります。

アルゴリズムは、可能なすべての一意の文字列を生成し、それらを並べ替えて最大の文字列を見つけるよりも効率的である必要があります。

注：これは宿題ではありません。

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 に答える