Beats 99.33% 🔥|| Simple and Easy Approach Using string
\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to find the lexicographically smallest subsequence of distinct char
\n![image.png](https://assets.leetcode.com/users/images/d5101daf-e86c-433f-8a77-92c60565fa3e_1704106524.6674483.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to find the lexicographically smallest subsequence of distinct characters\n that appears in the same order as the original string.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe use a greedy approach and a string  to build the smallest subsequence.\n        \n- We iterate through the characters in the original string.\n- If a character is already seen or has been added to the result, we skip it.\n- We remove characters from the end of the result if they are greater than the current character,\nhave remaining occurrences in the original string, and haven\'t been added to the result yet.\nWe add the current character to the result.\n\n# Complexity\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity :\nO(n) where n is the length of the input string\n\nSpace complexity:\n We use two arrays of size 26 (constant size), which contributes to O(26) or O(1) space.\nAdditionally, we use a StringBuilder to store the result, which can have a maximum length of n.\nTherefore, the overall space complexity is O(1 + n), which simplifies to O(n).\n\nNote: we can do this using  stack also\n\n\n# Code\n```\nclass Solution {\n    public String smallestSubsequence(String s) {\n        int n = s.length();\n        boolean[] seen = new boolean[26];\n        int[] frq = new int[26];\n\n        for (int i = 0; i < n; i++)\n            frq[s.charAt(i) - \'a\']++;\n\n        StringBuilder sb = new StringBuilder();\n\n        for (int i = 0; i < n; i++) {\n            char c = s.charAt(i);\n            frq[c - \'a\']--;\n\n            if (seen[c - \'a\'])\n                continue;\n\n            while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c && frq[sb.charAt(sb.length() - 1) - \'a\'] != 0) {\n                seen[sb.charAt(sb.length() - 1) - \'a\'] = false;\n                sb.deleteCharAt(sb.length() - 1);\n            }\n\n            sb.append(c);\n            seen[c - \'a\'] = true;\n        }\n\n        return sb.toString();\n    }\n}\n\n```
['String', 'Monotonic Stack', 'Java']