Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let me state the rules for ordering in a way that I think is more clear.</p> <p>String A is greater than string B if</p> <pre><code>- A is longer than B OR - A and B are the same length and A is lexicographically greater than B </code></pre> <p>If my restatement of the rules is correct then I believe I have a solution that runs in O(n^2) time and O(n) space. My solution is a greedy algorithm based on the observation that there are as many characters in the longest valid subsequence as there are unique characters in the input string. I wrote this in Go, and hopefully the comments are sufficient enough to describe the algorithm.</p> <pre><code>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) &gt; 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 &gt;= 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] &gt;= 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) } </code></pre> <p>I am fairly certain you can do this in O(n) time, but I wasn't sure of my solution so I posted this one instead.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind the lexicographically largest unique string
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USRunning Wild
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFind the lexicographically largest unique string
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COSorry for the confusion, the condition should be AND. The question has been edited.
      singulars
      1. PO
      1. USDraco
    2. COWell you can't have more characters and be equal length, so we are both saying the same thing.
      singulars
      1. PO
      1. USRunning Wild
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload