Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions.

For example if they give you "abc"
you print out
a
ab
abc
ac
b
bc
c

Now for the unique solution constraint, if they give you "aba" the output should be:
a
ab
aba
b

Question

Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions.

For example if they give you "abc"
you print out
a
ab
abc
ac
b
bc
c

Now for the unique solution constraint, if they give you "aba" the output should be:
a
ab
aba 
b

Dmytro · Accepted Answer

What about counting the number of each character in a string? for "aba" we have a-2, b - 1. now recursive solution which takes charecter, for a we choose 0a, 1a, and 2a and push to the 'b' where take 0b or 1b. now we have "", "a","aa","ab","b". all subsets + empty one.

Ker · Answer

So this requires subsets to be printed and not substrings; ordering of characters doesn't matter. So sort the characters and generate unique subsets.

import java.util.Arrays;
import java.util.Scanner;

public class UniqueSubsetGenerator {

	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		while (true) {
			System.out.println("Enter string : ");
			final String masterWord = in.nextLine();
			char[] word = masterWord.toCharArray();
			Arrays.sort(word);
			generateUniqueSubsets(word, 0, "");
		}
	}

	private static void generateUniqueSubsets(char[] word, int start, String prefix) {
		//System.out.println("start " + start + " prefix " + prefix);
		if (start >= word.length) {
			System.out.println(prefix);
			return;
		}
		
		char ch = word[start];
		int count = 1;
		for (int i=start+1; i

Sigiloso · Answer

@Marius: what do you mean by "sort the array"? There is no array in the question

Sigiloso · Answer

def uniqueSubsets(inpStr):
  inpStr = sorted(inpStr)
  subSets = []
  uniqueSubsetsHelper(subSets, "", 0, inpStr)
  return subSets

def uniqueSubsetsHelper(subSets, currSet, index, inpStr):
    if index == len(inpStr): subSets.append(currSet)
    if index >= len(inpStr): return
    charLen = getLen(index, inpStr)
    for i in range(charLen + 1):
        posSet = currSet + inpStr[index] * i
        uniqueSubsetsHelper(subSets, posSet, index + charLen, inpStr)

def getLen(index, inpStr):
    currChar = inpStr[index]
    currLen = 0
    while index < len(inpStr):
        if inpStr[index] == currChar:
            currLen += 1
        else:
            return currLen
        index += 1
    return currLen

Marius · Answer

@Allen: The interviewer specified that he wants a recursive solution and you are not allowed to use extra memory.

Note: The interviewer gave me a big hint: "What happens if you sort the array and simply generate all the subsets?"

Allen · Answer

There is a divide & conquer strategy with this problem. Divide string into two halves. Recursively print the string on left and then on right. Finally, for each string on left, combine it with every string on the right. (Note this will not give the unique solution.)

To obtain the unique solution, a simple way is to use a set to keep track of every substrings we have constructed. If element is already in the set, we simply not add it. In the end, we print out every element in the set. 

Maybe there is a better way without using extra memory.

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas