Last Updated: 13 Apr, 2021

Day 24 : Lexicographically Smallest Subsequence of Distinct Characters.

Easy

Asked in companies

Solve now

Problem statement

You have been given a string ‘S’. You need to return the lexicographically smallest subsequence of ‘S’ that contains all the distinct characters of ‘S’ exactly once. Return the string as mentioned above.

A string is a subsequence of a given string, that is generated by deleting some character of a given string without changing its order.

Example:

Let S = “ababc”. The lexicographically smallest subsequence containing all the distinct characters of strings is “abc”.

Note:

Strings consist of only lowercase characters.

You do not need to print anything; it has already been taken care of. Just implement the function.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the length of the string ‘S’.

The next line of the test case contains the string ‘S’.

Output Format:

For each test case return the lexicographically smallest subsequence of ‘S’ that contains all the distinct characters of ‘S’ exactly once.

Constraints:

1 <= T <= 10
1 <= N <= 1000

Time Limit: 1sec

Solve now

Approaches

01 Approach

Iterate over all the subsequences of string ‘S’:-

Declare a global string variable ‘ANS’.
Declare a function ‘BUILD_SUBSEQUENCE(string S, string W, int IDX)’ where ‘W’ stores the subsequence of string built till now and ‘IDX’ stores the index of character which will be considered now:-
- If ‘IDX’ == ‘N’ we have reached the end of string check if it is a valid subsequence by building counter array ‘CTR_S’ and ‘CTR_W’ which stores the frequency of lowercase alphabets in ‘S’ and ‘W’:-
  - Declare a variable ‘CHECK’ and initialize it with one.
  - Iterate over ‘CTR_S’. If ‘CTR_S’ is greater than zero and ‘CTR_W’ is not one initialize ‘CHECK’ with zero.
  - If ‘CHECK’ is 1 and either ‘ANS’ is empty or ‘W’ is lexicographically smaller than ‘ANS’ then initialize ‘ans’ with ‘W’.
- We can either take the character at ‘IDX’ or don’t take it:-
  - Recursively call function ‘BUILD_SUBSEQUENCE(S, W, IDX + 1)’ - In this case, we don’t take the character at index ‘IDX’.
  - Update ‘W’ by ‘W’ += ‘S[IDX]’. Recursively call function ‘BUILD_SUBSEQUENCE(S, W, idx + 1)’ - In this case we take character at index ‘IDX’.
Initialize ‘ANS’ with the empty string.
Call the function ‘BUILD_SUBSEQUENCE(S, “, 0)’ because initially subsequence is empty and we will start building from index 0.
Return ‘ANS’.

Solve now

02 Approach

We can find the last occurrence for each character. We can use a stack to keep the characters for the result. We can iterate on the string ‘S’. If the current character is not present in the stack, pop the top of the stack till the element on the top element is greater than the current character and will occur later in the string ‘S’ and mark them as unvisited. We do this because this helps in building lexicographically smaller subsequence. Push the current character in the stack. Mark the current character as visited.

We will implement this as follows:-

Declare an array ‘LAST_IDX’ of size 26 which stores the last occurrence of each character if it has occurred otherwise -1.
Declare an array ‘VIS’ of size 26 and initialize all elements with ‘false’.
Declare a stack ‘W’.
Iterate string ‘S’ and do as follows:-
- If ‘VIS[ S[i] - ‘a’]’ is false:-
  - Run a while loop till the top of the stack is greater than the current character and the last index of the top element of the stack is greater than ‘i’ pop the top element and mark it as unvisited.
  - Push the current character in the stack. Mark ‘VIS[ S[i] - ‘a’]’ as true.
Declare string ‘ANS’. Pop the elements from the stack and append them to the back of ‘ANS’.
Return ‘ANS’.

Solve now