Distinct Characters

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
Expedia GroupWalmartThink Future Technologies

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'].

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
aba
xyz
Sample Output 1:
a
a
ab
b
ba
x
xy
xyz
xz
y
yz
z

Explanation For Sample Output 1:

In the first case, 
The only valid sequences of length one are “a” -> 2 times, “b” -> 1 time. For length two, “ab” and “ba” both occur only once. There is no valid sequence possible for length three as the only subsequence of length three is “aba” which is not valid. Hence, the answer is the list of all 5 subsequences created.

In the second case, 
The only valid sequences of length one are “x”, “y” and “z”. For length two, “xy”, “xz” and “yz” are valid. For length three “xyz” is valid. Note that repetition is not possible in this case as there are no characters that occur multiple times. Hence, the answer is the list of all 7 subsequences created.
Sample Input 2:
2
abca
zzz
Sample Output 2:
a
a
ab
abc
ac
b
ba
bc
bca
c
ca
z
z
z
Hint

Do the constraints allow us to generate all subsequences of the string?

Approaches (1)
Brute Force

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”.
Time Complexity

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

 

Since we iterate through 2 ^ N different possibilities and each possibility has a length of at most N, the time complexity is O(2 ^ N * N).

Space Complexity

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

Since we store at most 2 ^ N different possibilities and each possibility has a length of at most N, the space complexity is O(2 ^ N * N).

Code Solution
(100% EXP penalty)
Distinct Characters
Full screen
Console