CODEWITHSUNDEEP
arraysstringalgorithmdata-structures
kumarmo2
kumarmo2

Reputation: 1393

Remove Duplicate characters

The problem i am facing 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 thought of few approaches but still not able to crack the problem. The link to the problem is leetcode

I dont want any code in solution but the approach i can take to solve the question only. Thanks in advance.

Update: Will add the approach i took(which is wrong/incomplete by the way)

Will save the last positions of each character in the string in some data structure. after that will start processing the characters in the ascending order of their last position.Eg : in first iteration the character with the minimum last position is processed. i thought i will iterate through the string up untill last position of the character i am processsing and will remove few characters on some conditions(like if the character while looping is less than the character with min Last position and other was same only but greater than it). but all were failing only.

Upvotes: 1

Views: 121

Answers (3)

Peter de Rivaz
Peter de Rivaz

Reputation: 33519

Algorithm

Your approach sounds like it is almost there.

The first steps sound good:

Save the last positions of each character in the string in some data structure. after that will start processing the characters in the ascending order of their last position.

in first iteration the character with the minimum last position is processed.

In your example "cbacdcbc", the minimum last position is 3, the location of the a.

The first letter of the string will be equal to the minimum character in these first 3 positions (in this case, the letter a).

Now you can repeat this procedure starting from the letter after the one you just picked. So in this case "cdcbc". The only difference is that you can now ignore the last positions for any letters that you have picked as you are not allowed to pick these again.

Explanation

Consider choosing the first letter of the output. We want to know the smallest it can be. To make it small we need to delete characters before it in the string, but we must not delete a character if it is the last occurrence (because this will make it impossible to satisfy the constraints).

Therefore we know that we can safely delete characters up to the minimum last position, and we wish to know what is the smallest the first character of the output can be, therefore we should just pick the smallest in the allowed range. (If there is are more than one of the smallest, then pick the earliest.)

Upvotes: 1

sparrowTrajon
sparrowTrajon

Reputation: 180

Hi you can use the hash table

lets say this is the string "cbacdcbc"

create a array of length 26, fill all 0 in the array. Now iterate throght the string and place each character in array at index value of characters ascii value, sort out the array and you done with the problem.

say int a[26];

a['c']= valuse of c here;

Upvotes: 0

thehuijb
thehuijb

Reputation: 229

you could use the Set type depending on the language u are using. Something like a SortedSet would probably solve your problem

Upvotes: 0

Related Questions