Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to get the smallest in lexicographical order?

Tags:

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

like image 381
allencharp Avatar asked Dec 30 '15 14:12

allencharp


People also ask

How do you find the lexicographically smallest?

The task is to find the lexicographically smallest string possible by inserting a given character. A string a is lexicographically smaller than string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

How do you find the lexicographically smallest array?

Approach: In order to get the lexicographically smallest array, we can choose the minimum element as the first element but that will not satisfy the condition where the first element has to be strictly greater than the second element.

How do you find the lexicographically smallest string between two strings?

Note: string S = s1s2… sn is said to be lexicographically smaller than string T = t1t2… tn, if there exists an i, such that s1 = t1, s2 = t2, … si – 1 = ti – 1, si < ti.

What is the smallest lexicographical order?

Thanks for the answer in advance :) 6 Answers 6. The smallest lexicographical order is an order relation where string s is smaller than t, given the first character of s (s 1) is smaller than the first character of t (t 1), or in case they are equivalent, the second character, etc.

How to get the smallest lexicographic array?

Lexicographic or Lexicographically means sorting in the natural order / dictionary order. In the case of getting smallest lexicographical array is to get the smallest possible array by lexographic comparison. E.g.: How to get the smallest in lexicographical order? I need help in finding the lexicographically smallest string.

How to find the lexicographically smallest and largest substring from a string?

Write a program to find the lexicographically smallest and largest substring from given string ‘s’ of the length ‘k’. Basically you have to find out all the sub-strings and then sort them in lexicographical order. Some times lexicography order is also called an alphabetical order or dictionary order.

What is lexicography order in Python?

Some times lexicography order is also called an alphabetical order or dictionary order. Note: Block letters come first in the lexicographic order and then small letters. Given String: csestack Lexicographically Smallest Substring: "ack" Lexicographically Largest Substring: "tac" Suppose you’re given a String s=”csestack” and given the integer k=3.


1 Answers

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.

like image 64
Willem Van Onsem Avatar answered Sep 19 '22 12:09

Willem Van Onsem