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);
}
}
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);
}
}