1159. Smallest Subsequence Of Distinct Characters¶

Difficulty: Medium

1159. Smallest Subsequence of Distinct Characters

Medium

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Solution¶

class Solution {
    public String smallestSubsequence(String s) {
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++) lastIndex[s.charAt(i) - 'a'] = i; 
        boolean[] seen = new boolean[26]; 
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            int currentChar = s.charAt(i) - 'a';
            if (seen[currentChar]) continue; 
            while (!stack.isEmpty() && stack.peek() > currentChar && i < lastIndex[stack.peek()]) seen[stack.pop()] = false;
            stack.push(currentChar); 
            seen[currentChar] = true;
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) result.append((char) (stack.pop() + 'a'));
        return result.reverse().toString();
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here