Найти лексикографически наибольшую уникальную строку

Question

Мне нужен алгоритм для поиска наибольшей уникальной (без дубликатов символов) подстроки из строки путем удаления символа (без переупорядочения).

Строка A больше, чем String B, если она удовлетворяет этим двум условиям.

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

Например, если входной является строка Dedede, то возможные уникальные комбинации де, ред, д и е.
Из этих комбинаций, самый большой один поэтому ред, поскольку она имеет больше символов, чем д и е и лексикографически больше, чем де.

Алгоритм должен быть более эффективным, чем генерировать все возможные уникальные строки и сортировать их, чтобы найти самый большой.

Примечание: это не домашнее задание.

Answer 1

Позвольте мне изложить правила для заказа таким образом, который, я думаю, более ясен.

Строка больше, чем строка 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 времени (п), но я не был уверен в своем решении, так что я отправил это одно вместо.

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

Это код snipet просто дает lexicigraphically большую строку. Если вы не хотите дубликатов, вы можете просто отслеживать уже добавленные символы.