Suchen Sie die lexikografisch größte eindeutige Zeichenfolge

Question

Ich brauche einen Algorithmus, um die größte eindeutige Teilzeichenfolge (keine doppelten Zeichen) aus einer Zeichenfolge durch Entfernen von Zeichen (keine Neuanordnung) zu finden.

Zeichenfolge A ist größer als Zeichenfolge B, wenn sie diese beiden Bedingungen erfüllt.

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

Zum Beispiel, wenn die Eingabezeichenfolge ist dedede, dann sind die möglichen eindeutigen Kombinationen sind de, ed, d und e.
Von diesen Kombinationen ist die größte daher ed, da es mehr Zeichen als d und e und lexikographisch größer als de hat.

Der Algorithmus muss effizienter sein als das Erzeugen aller möglichen eindeutigen Strings und das Sortieren nach dem größten.

Hinweis: Dies ist keine Hausaufgabe.

Answer 1

Lassen Sie mich die Regeln für die Bestellung in einer Weise, die ich denke, ist klarer.

String A größer als String B, wenn

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

Wenn meine Neuformulierung der Regeln korrekt ist, dann glaube ich, dass ich eine Lösung, die in O läuft (n^2) Zeit und O (n) Raum . Meine Lösung ist ein Greedy-Algorithmus, der auf der Beobachtung basiert, dass in der längsten gültigen Teilsequenz so viele Zeichen vorhanden sind wie eindeutige Zeichen in der Eingabezeichenfolge. Ich habe das in Go geschrieben, und hoffentlich reichen die Kommentare aus, um den Algorithmus zu beschreiben.

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) 
} 

Ich bin ziemlich sicher, dass Sie dies in O (n) Zeit tun, aber ich war nicht sicher, ob meine Lösung so gepostet ich diese stattdessen.

Answer 2

Wie über diese

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;  
    } 

Dieser Codestück ist nur gibt Ihnen die lexicigraphically größeren String. Wenn du keine Duplikate willst, kannst du einfach nur die bereits hinzugefügten Charaktere verfolgen.