Smallest Substring Program in Java

The program must accept a string as the input. The program must print the smallest substring containing all the distinct characters of the string S in it.
Note: If more than one such substring is found, print the first occurring substring.

Boundary Condition(s):
1 <= Length of string S <= 100

Input Format:
The first line contains the value of S.

Output Format:
The first line contains the smallest substring with all the distinct characters of the string S.

Example Input/Output 1:
Input:
aabbcccdddd

Output:
abbcccd

Explanation:
Here the distinct characters are aband d.
The smallest substring with all the characters aband is abbcccd.
Hence abbcccdis printed as the output.

Example Input/Output 2:
Input:
jsajdnskjd

Output:
ajdnsk

import java.util.*;
public class Hello {
    static final int MAX_CHARS =256;
    static String findsub(String str){
        int n=str.length();
        int dist=0;
        boolean[] visited = new boolean[MAX_CHARS];
        Arrays.fill(visited,false);
        for(int i=0;i<n;i++){
            if(visited[str.charAt(i)]==false){
                visited[str.charAt(i)]=true;
                dist++;
            }
        }
        int start=0, index=-1;
        int minlen=Integer.MAX_VALUE;
        int count=0;
        int[] curr=new int[MAX_CHARS];
        for (int j=0;j<n;j++){
            curr[str.charAt(j)]++;
            if(curr[str.charAt(j)]==1)count++;
            if(count == dist){
                while(curr[str.charAt(start)]>1){
                    if (curr[str.charAt(start)]>1) curr[str.charAt(start)]--;
                    start++;
                }
                int lenwindow=j-start+1;
                if(minlen>lenwindow){
                    minlen=lenwindow;
                    index=start;
                }
            }
        }
        return str.substring(index,index+minlen);
    }
    public static void main(String[] args) {
Scanner s= new Scanner(System.in);
String str=s.nextLine();
System.out.println(findsub(str));
}
} 
Previous Article

Inverted Trapezium Pattern Program In C

Next Article

Last and First Character Words

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *