Day 24 : Lexicographically Smallest Subsequence of Distinct Characters.

Easy
0/40
Average time to solve is 20m
profile
Contributed by
8 upvotes
Asked in companies
Expedia GroupAmazonOla

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
7
aababcb
5
bcabb
Sample Output 1:
abc
bca

Explanation For Sample Input 1:

Test case 1:

The lexicographically smallest subsequence contains all the distinct characters of strings is “abc”. 

Therefore the answer is “abc”.

Test case 2:

The lexicographically smallest subsequence contains all the distinct characters of strings is “bca”.

Therefore the answer is “bca”.
Sample Input 2:
2
7
gggjhhh
8
laughhgu
Sample Output 2:
gjh
laghu
Hint

Brute Force. 

Approaches (2)
Brute Force 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’.
Time Complexity

O(N * 2 ^ N), where ‘N’ denotes the length of the string.

 

As we are iterating over all the subsequences of string and for each subsequence we are iterating ‘S’ which is of length ‘N’.

Space Complexity

O(N), where ‘N’ denotes the length of the string.

 

As we recurse we build a string of length ‘N’.

Code Solution
(100% EXP penalty)
Day 24 : Lexicographically Smallest Subsequence of Distinct Characters.
Full screen
Console