CC-6 :Find all unique sub sequences that can be formed from characters of a String.

Description:

Given an input String str, find and return all unique subsequences that can be formed by the characters of str.

Test cases and expected outputs:

Input Parameters	Expected outputs
str=”sugar”	Subsequences: : a,su,sug,g,suga,uga,ar,ug,r,s,u,ugar,gar,ga,sugar
str=”morning”	Subsequences: : ornin,ning,mor,mornin,nin,rnin,rning,mo,or,ing,in,g,i,orn,orni,rni,m,morn,n, morning ,o,r,orning,ng,ni,rn,morni

Pseudocode:

The java method should accept following input parameters: str (String).

Initialize a variable set of type HashSet to hold the unique subsequences that can be formed from str.

Using a for loop iterate through str, using idx1 as a loop variable with initial value 0 and increment idx1 till it reaches str.length()-1:

Using a for loop iterate through str, using idx2 as a loop variable with initial value idx1+1 and increment idx2 till it reaches str.length()-1:

Using String.substring() method, extract a substring from str with start index idx1 and end index str2.

Add the extracted substring to set.

At completion of above loop, set contains all the unique subsequences of str.

Use an iterator to access elements from set and add the same to String array named retSubArr. Return retSubArr.

Code:

public boolean setArraysCheckDisjoint(String[] arr1, String[] arr2) {
	HashSet<String> set1=new HashSet<String>();
	for (int idx=0; idx < arr1.length; idx++) {
		set1.add(arr1[idx]);
	}
	for (int idx=0; idx < arr2.length; idx++) {
		if(set1.contains(arr2[idx])) {
			return false;
		}
	}
	return true;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.HashSet;


public class SetArraysCheckDisjoint {
	
public boolean setArraysCheckDisjoint(String[] arr1, String[] arr2) {
	HashSet<String> set1=new HashSet<String>();
	for (int idx=0; idx < arr1.length; idx++) {
		set1.add(arr1[idx]);
	}
	for (int idx=0; idx < arr2.length; idx++) {
		if(set1.contains(arr2[idx])) {
			return false;
		}
	}
	return true;
}

	
public static void main(String[] args) {
	SetArraysCheckDisjoint sp=new SetArraysCheckDisjoint();
	boolean retVal;
	try {
	String[] strArray1 = {"hi", "hello", "hola"};
	String[] strArray2 = {"good", "better", "best"};
	printArraySummary(strArray1, "Original Array1");
	printArraySummary(strArray2, "Original Array2");
	retVal=sp.setArraysCheckDisjoint(strArray1, strArray2);
	if (retVal==true) {
		System.out.println("\n The arrays are disjoint !\n");		
	}else {
		System.out.println("\n The arrays are *not* disjoint !\n");	
	}
	String[] strArray3 = {"great", "big", "ship"};
	String[] strArray4 = {"small", "fast", "boat"};
	printArraySummary(strArray3, "Original Array1");
	printArraySummary(strArray4, "Original Array2");
	retVal=sp.setArraysCheckDisjoint(strArray3, strArray4);
	if (retVal==true) {
		System.out.println("\n The arrays are disjoint !\n");		
	}else {
		System.out.println("\n The arrays are *not* disjoint !\n");	
	}
			
	String[] strArray5 = {"north", "south", "east"};
	String[] strArray6 = {"west", "north", "east"};
	printArraySummary(strArray5, "Original Array1");
	printArraySummary(strArray6, "Original Array2");
	retVal=sp.setArraysCheckDisjoint(strArray5, strArray6);
	if (retVal==true) {
		System.out.println("\n The arrays are disjoint !\n");		
	}else {
		System.out.println("\n The arrays are *not* disjoint !\n");	
	}
			
	}catch (Exception exception) {
	System.out.print("Exception,"+ exception);
	exception.printStackTrace();
				
	}
}
			
public static void printArraySummary(String[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex< intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("*************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}				
		
		

}