Last Updated: 8 May, 2021

Distinct Characters

Moderate

Asked in companies

Solve now

Problem statement

Given a string “STR”, you need to return all the possible non-empty subsequences with distinct characters. You can return the strings in any order.

Note:

If the same string can be generated multiple times, return them multiple times.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

For eg. Let the input string be 'cbc'. Then all the subsequences with distinct characters will be - ['c', 'bc', 'c', 'cb', 'b'].

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first and the only line of each test case contains the string 'STR'.

Output Format :

For each test case, print all the substrings with distinct characters.

Output for each test case will be printed in a new line.

Note:

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

Constraints:

1 <= T <= 100
1 <= |STR| <= 15

Where |STR| denotes the length of “STR”

String “STR” will only consist of lowercase English Alphabets.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We can generate all possible subsequences of the string, and for each subsequence check if it contains any character multiple times. If it doesn’t contain any character multiple times, append it into our result.

Algorithm:

Create a variable “mask”, and iterate from 0 till 2 ^ |STR| - 1.
- For each value of “mask”, if the ith bit in “mask” is set, it means we are including the ith character of “STR” into our current string.
- Each value of “mask” corresponds to exactly one subsequence and vice versa. Insert all the substrings generated into a list “subsequences”.
Iterate through each string in “subsequences”.
- Iterate through the current subsequence and check if it has repeating characters.
- We can check for repeating characters by storing the characters visited in a hashset, and if at any position the current character is already present in the hashset, we will not include it in the result.
- If it doesn’t have repeating characters, insert it into a list “result”.
Return “result”.

Solve now