CODEWITHSUNDEEP
algorithm
allencharp
allencharp

Reputation: 1161

How to get the smallest in lexicographical order?

I am doing a leetcode exercise

https://leetcode.com/problems/remove-duplicate-letters/

The question is:

# Given a string which contains only lowercase letters, remove duplicate
# letters so that every letter appear once and only once. You must make
# sure your result is the smallest in lexicographical order among all possible results.
#
# Example:
# Given "bcabc"
# Return "abc"
#
# Given "cbacdcbc"
# Return "acdb"

I am not quite sure about what is the smallest in lexicographical order and why Given "cbacdcbc" then the answer would be "acdb"

Thanks for the answer in advance :)

Upvotes: 38

Views: 83232

Answers (6)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477200

The smallest lexicographical order is an order relation where string s is smaller than t, given the first character of s (s1) is smaller than the first character of t (t1), or in case they are equivalent, the second character, etc.

So aaabbb is smaller than aaac because although the first three characters are equal, the fourth character b is smaller than the fourth character c.

For cbacdcbc, there are several options, since b and c are duplicates, you can decided which duplicates to remove. This results in:

cbacdcbc = adbc
cbacdcbc = adcb
cbacdcbc = badc
cbacdcbc = badc
...

since adbc < adcb, you cannot thus simply answer with the first answer that pops into your mind.

Upvotes: 34

Dewfy
Dewfy

Reputation: 23634

String comparison usually can be done in 2 ways:

  • compare for first unmatched letter (called lexicographical ) for example aacccccc is less than ab because at second position b has been met (and a < b).
  • compare string length first and shorter string is treated as less. If strings length are equal then apply lexicographical.

Second one may be faster if length of strings are known.

You question contains small error:

why Given "bcabc" then the answer would be "acdb"

While origin was: "Given "bcabc" Return "abc"". That make sense that abc should be returned instead of bca

Upvotes: 1

MBo
MBo

Reputation: 80257

the smallest in lexicographical order - your answer should be a subsequence of initial string, containing one instance of every char.
If there are many such subsequences possible (bca, bac, cab, abc for the first example), return the smallest one, comparing them as strings (consider string order in vocabulary).

why Given "bcabc" then the answer would be "acdb"
You confused two different examples

Upvotes: 0

dlask
dlask

Reputation: 8992

You cannot reorder characters. You can only choose which occurrence to remove in case of duplicated characters.

bcabc

We can remove either first b or second b, we can remove either first c or second c. All together four outputs:

..abc
.cab.
b.a.c
bca..

Sort these four outputs lexicographically (alphabetically):

abc
bac
bca
cab

And take the first one:

abc

Upvotes: 17

Or Yaniv
Or Yaniv

Reputation: 571

clearly, the wanted output must contain only letter once. now, from what i understand, you must pick the letters in a manner that will give you the best order when the leftmost letters come before in (abc? ascii?) now you'd ask why "acdb" than and not "abcd". i think you don't take the first "cb" since you more c and b later, but you're have to take the "a" since there's only one coming now. then you must take c 'cause there are no more "d" after the next b. that's why you take c, and then d because no more d's later.

in short, you want to take it with best lexicographical order from low to high, but make sure you take all the letters while iterating over the input string.

Upvotes: 1

Codor
Codor

Reputation: 17605

There seems to be some misunderstanding; the example states that for the input bcabc, the expected output should be abc, not acdb, which refers to the input cbacdcbc.

Upvotes: 0

Related Questions