Smallest Subsequence of Distinct Characters

• Define a recursive function, say solve(s).
• Base Case: If s is empty, return an empty string.
• Find the last occurrence index for each character in s.
• Find the index pos of the lexicographically smallest character in s up to the point where a character appears for the last time.
  • Iterate through s from left to right. Keep track of the index pos of the smallest character seen so far.
  • If we encounter a character c which is the last of its kind in s (i.e., its last occurrence index is the current index), we must make a choice from the prefix of s we have scanned so far. The best choice is the character at pos.
• Let the chosen character be ch = s.charAt(pos).
• Form a new string s_rem by taking the substring of s after pos and removing all occurrences of ch.
• Return ch + solve(s_rem).

The function findSmallest(s) aims to find the smallest subsequence for a given string s. At each step, we must decide which character to pick first. The ideal first character is the smallest one ('a'), but we can only pick it if the remaining unique characters all appear later in the string. We generalize this: we find the smallest character c in s such that the suffix of s after c contains all other required unique characters.

To implement this, we can find the last occurrence of every character. Then, we iterate through the string to find the smallest character up to the earliest last-occurrence position. This character is the guaranteed best first character for our subsequence. For example, in "cbacdcbc", the last 'a' is at index 2. We must pick a character from "cba". The smallest is 'a', so we pick 'a'.

Once we've chosen the first character c (at index i), we append it to our result. Then, we recursively call the function on the rest of the string s.substring(i+1), but we must remove all occurrences of c from this substring since we've already used it. The base case for the recursion is when the input string is empty.

1class Solution {2    public String smallestSubsequence(String s) {3        if (s.isEmpty()) {4            return "";5        }6        7        // Find the last position of each character8        int[] lastPos = new int[26];9        for (int i = 0; i < s.length(); i++) {10            lastPos[s.charAt(i) - 'a'] = i;11        }12        13        int pos = 0; // Position of the smallest character for the first part of the result14        for (int i = 0; i < s.length(); i++) {15            // Find the lexicographically smallest character16            if (s.charAt(i) < s.charAt(pos)) {17                pos = i;18            }19            // If we are at the last occurrence of a character, we must decide.20            // The smallest character in s[0...i] must be chosen.21            if (i == lastPos[s.charAt(i) - 'a']) {22                break;23            }24        }25        26        char ch = s.charAt(pos);27        // Recursively call on the substring after the chosen character,28        // removing all other occurrences of the chosen character.29        String remainingString = s.substring(pos + 1).replaceAll(String.valueOf(ch), "");30        31        return ch + smallestSubsequence(remainingString);32    }33}

• Create an array lastIndex of size 26 to store the last occurrence index of each character in s.
• Initialize an empty stack stack to build the result.
• Initialize a boolean array seen of size 26 to keep track of characters already in the stack.
• Iterate through the input string s from left to right with index i and character c:
  • If seen[c - 'a'] is true, continue to the next character.
  • While the stack is not empty, the character at the top of the stack is lexicographically greater than c, AND the last occurrence of the top character is after the current index i:
    • Pop the character from the stack.
    • Mark the popped character as not seen (e.g., seen[popped_char - 'a'] = false).
  • Push the current character c onto the stack.
  • Mark c as seen (e.g., seen[c - 'a'] = true).
• After the loop, build a string from the characters in the stack. This string is the result.

The core idea is to maintain a candidate result (using a stack) that is always the lexicographically smallest possible subsequence of the prefix of s we have processed so far.

We iterate through the string s. For each character c:

• If c has already been included in our result stack, we skip it. This ensures each character appears only once.
• If c is not in the stack, we need to add it. Before adding, we check if the character at the top of the stack is greater than the current character c. If it is, and if that top character appears again later in the string s, we can pop it from the stack. Popping a larger character in favor of a smaller one (c) helps in creating a lexicographically smaller result. We repeat this popping process as long as the conditions are met.
• After the popping phase, we push the current character c onto the stack.

To efficiently check if a character appears again later, we can pre-process the string to find the last occurrence index of each character. We also use a boolean array or a set to keep track of the characters currently in the stack for O(1) lookup. After iterating through the entire string, the characters in the stack, when joined together, form the desired smallest subsequence.

1import java.util.Stack;2 3class Solution {4    public String smallestSubsequence(String s) {5        int[] lastIndex = new int[26];6        for (int i = 0; i < s.length(); i++) {7            lastIndex[s.charAt(i) - 'a'] = i;8        }9        10        boolean[] seen = new boolean[26];11        Stack<Character> stack = new Stack<>();12        13        for (int i = 0; i < s.length(); i++) {14            char c = s.charAt(i);15            if (seen[c - 'a']) {16                continue;17            }18            19            while (!stack.isEmpty() && c < stack.peek() && i < lastIndex[stack.peek() - 'a']) {20                seen[stack.pop() - 'a'] = false;21            }22            23            stack.push(c);24            seen[c - 'a'] = true;25        }26        27        StringBuilder sb = new StringBuilder();28        for (char c : stack) {29            sb.append(c);30        }31        return sb.toString();32    }33}