Sunday 28 April 2019

Shortest distinct characters sub string from original string

package org.liferayasif;

public class ShortestSubStringAllChars {

public static void main(String[] args) {

//By default original string is lower case alphabets
String originalString = "dfadsaaa";

//validation for string must not empty
if(originalString==null || originalString.length()==0) {
System.out.println("Please provide string of length > 0");
return ;
}

//get distinct string from original string
String distinctString = getDistinctString(originalString);
System.out.println("distinctString: "+distinctString);

//sorted distinct string in ascending order
String sortedDistinctString = sort(distinctString);
System.out.println("distinctString after sorting: "+sortedDistinctString);

int numOfDistinctChars = distinctString.length();

int subStringStartingIndex = 0;
int subStringEndingIndex = numOfDistinctChars;

boolean flag = false;

for(int j=0 ; j<originalString.length() ; j++) {

subStringStartingIndex = 0;

if(j!=0) {
subStringEndingIndex = numOfDistinctChars + j;
}

for(;;) {

/*getting substring from original string starting from 0 to distinct string length
* then shifting location of substring one by one
* e.g len of distinct string = 4 then will get substring from original string of size
* 4 and get all substring of size 4 till end of substring, if all distinct characters
* not found in this range then increasing substring size by one and again same operation
* shifting from left to right one by one
*/
String subString = originalString.substring(subStringStartingIndex, subStringEndingIndex);
System.out.println("subString: "+subString );

//get distinct characters substring from original substring
String distinctSubString = getDistinctString(subString);

//sort distinct sub string
String distinctSortedSubString = sort(distinctSubString);

/*compare sorted distinct string with sorted distinct sub string
* if match then this substring having all distinct characters
* which we requires
* once found we break infinite loop
* and set a flag to break outer loop
*/
if(distinctSortedSubString.equals(sortedDistinctString)) {
System.out.println("found: "+subString.length() + "   "+j+ "  "+subStringStartingIndex+" "+subString);
flag = true;
break;
}
/*to avoid index out of bound exception we have to check length of end substring index
* and if it reach to length of original string then finish the inner loop
*/
if(subStringEndingIndex==originalString.length()) {
break;
}
subStringEndingIndex +=1;
subStringStartingIndex++;
}
//to break outer loop if found solution
if(flag) {
break;
}
}
}

//Get distinct characters string from original string
private static String getDistinctString(String originalString) {

char[] ca = originalString.toCharArray();
String res = "";

res = res + ca[0];

for(int i=1 ; i<originalString.length() ; i++) {
if(!res.contains(ca[i]+"")) {
res = res + ca[i];
}
}
return res;
}

//Sort string in ascending order
private static String sort(String originalString) {

char[] ca = originalString.toCharArray();

for(int i=0 ; i<originalString.length() ; i++) {

for(int j=i+1 ; j<originalString.length() ; j++) {
if(ca[i]-ca[j]>=0) {
char t = ca[i];
ca[i] = ca[j];
ca[j] = t;
}
}
}
return new String(ca);
}

}