Distinct Characters
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

Question

Distinct Characters

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

Accepted Answer

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

Space Complexity: OtherExplanation:

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).

Time Complexity: OtherExplanation:

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).

Java (SE 1.8)

/*

    Time Complexity : O(2 ^ N * N)

    Space Complexity : O(2 ^ N * N)



    where 'N' denotes the length of the string.

*/



import java.util.*;

public class Solution 

{

    

    // Helper function to check if all characters

	// in a string are distinct

    public static Boolean allDistinctCharacters(String s)

    {



        // Initially no character is done

        Boolean[] done = new Boolean[26];

        Arrays.fill(done, Boolean.FALSE);

        for (int c = 0; c < s.length(); c++)

        {



            // If this character is done, there is a repeating character

            if (done[(s.charAt(c) - 'a')])

            {

                return false;

            }



            // Mark this character as done

            done[s.charAt(c) - 'a'] = true;

        }



        // Return true as we didn't find a repeating character

        return true;

    }

    

	public static ArrayList distinctCharacters(String str) 

    {

		

        // Store the length of the string

        int n = str.length();



        // Initialize our result as an empty list

        ArrayList result = new ArrayList<>();



        // Each mask represents a different subsequence

        for (int mask = 1; mask < (1 << n); mask++)

        {



            // Calculating our current subsequence

            String subsequence = "";

            for (int i = 0; i < n; i++)

            {



                // If the ith bit is set, include the ith

                // character in our subsequence

                if ((mask & (1 << i)) > 0)

                {

                    subsequence += str.charAt(i);

                }

            }



            // If all characters are distinct insert it into result

            if (allDistinctCharacters(subsequence))

            {

                result.add(subsequence);

            }

        }



        // Return the result

        return result;

	}

}

Python (3.5)

'''

    Time Complexity : O((2 ^ N )* N)

    Space Complexity : O((2 ^ N) * N)



    where 'N' denotes the length of the string.

'''



# Helper function to find if a string contain multiple characters.

def allDistinctCharacters(s):

    done = set()



    for c in s:

        if(c in done):

            return False



        done.add(c)

    

    return True



def distinctCharacters(str):



    n = len(str)



    # To store all resulting srtings.

    ans = []



    # Start with 1.

    mask = 1



    # Run a loop until we covered all subsequences.

    while(mask < ( 1 << n)):



        subseq = ""



        for i in range(n):

            if(mask & (1 << i)):

                subseq += str[i]

        

        # If subseq doesn't contain repeating character.

        if(allDistinctCharacters(subseq) == True):

            ans.append(subseq)

        

        # Increment mask.

        mask += 1

    



    # Return answer array.

    return ans

C++ (g++ 5.4)

/*

    Time Complexity : O(2 ^ N * N)

    Space Complexity : O(2 ^ N * N)



    where 'N' denotes the length of the string.

*/



// Helper function to check if all characters

// in a string are distinct

bool allDistinctCharacters(string s)

{



    // Initially no character is done

    vector done(26, false);

    for (int c = 0; c < s.size(); c++)

    {



        // If this character is done, there is a repeating character

        if (done[s[c] - 'a'])

        {

            return false;

        }



        // Mark this character as done

        done[s[c] - 'a'] = true;

    }



    // Return true as we didn't find a repeating character

    return true;

}





// Function to return all subsequences with distinct characters

vector distinctCharacters(string str)

{



    // Store the length of the string

    int n = str.size();



    // Initialize our result as an empty list

    vector result;



    // Each mask represents a different subsequence

    for (int mask = 1; mask < (1 << n); mask++)

    {



        // Calculating our current subsequence

        string subsequence = "";

        for (int i = 0; i < n; i++)

        {



            // If the ith bit is set, include the ith

            // character in our subsequence

            if (mask & (1 << i))

            {

                subsequence += str[i];

            }

        }



        // If all characters are distinct insert it into result

        if (allDistinctCharacters(subsequence))

        {

            result.push_back(subsequence);

        }

    }



    // Return the result

    return result;

}

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:

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:

Output Format :

Note:

Constraints:

Top Think Future Technologies Software Developer interview questions & answers

Popular interview questions of Software Developer