/316. Remove Duplicate Letters

316. Remove Duplicate Letters

Medium
Strings52.9% acceptance

Given a string input_str consisting of lowercase English letters, return a string containing each letter from input_str exactly once, such that the resulting string is the smallest possible in lexicographical order among all possible results. The order of characters in the output must be determined by this lexicographical minimization.

Example 1

Input: "zxyzzx"

Output: "xyz"

Explanation: Remove duplicates and arrange to get lex smallest: xyz.

Example 2

Input: "edcbaedcba"

Output: "abcde"

Explanation: All letters appear twice, lex smallest is abcde.

Constraints

  • 1 <= len(input_str) <= 104
  • input_str consists only of lowercase English letters
Python (current runtime)

Case 1

Input: "abacb"

Expected: "abc"

Case 2

Input: "aabbcc"

Expected: "abc"

Case 3

Input: "gfedcba"

Expected: "abcdefg"

Case 4

Input: "bbaac"

Expected: "bac"

Case 5

Input: "qwertyqwerty"

Expected: "ertyqw"