Minimize length of Substrings containing at least one common Character | Java program to implement the above approach ; Function to check and return if subStrings of length mid has a common character a ; Length of the String ; Initialise the first occurrence of character a ; Check that distance b / w the current and previous occurrence of character a is less than or equal to mid ; If distance exceeds mid ; Function to check for all the alphabets , if subStrings of length mid have a character common ; Check for all 26 alphabets ; Check that char i + a is common in all the subStrings of length mid ; If no characters is common ; Function to calculate and return the minm length of subStrings ; Initialise low and high ; Perform binary search ; Update mid ; Check if one common character is present in the length of the mid ; Returns the minimum length that contain one common character ; Function to check if all characters are distinct ; Driver Code
import java . util . * ; class GFG { static boolean check ( char [ ] str , int mid , char a ) { int n = str . length ; int previous = - 1 , i ; for ( i = 0 ; i < n ; ++ i ) { if ( str [ i ] == a ) { if ( i - previous > mid ) { return false ; } previous = i ; } } if ( i - previous > mid ) return false ; else return true ; } static boolean possible ( char [ ] str , int mid ) { for ( int i = 0 ; i < 26 ; ++ i ) { if ( check ( str , mid , ( char ) ( i + ' a ' ) ) ) return true ; } return false ; } static int findMinLength ( char [ ] str ) { int low = 1 , high = str . length ; while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( possible ( str , mid ) ) high = mid - 1 ; else low = mid + 1 ; } return high + 1 ; } static boolean ifAllDistinct ( String str ) { HashSet < Character > s = new HashSet < Character > ( ) ; for ( char c : str . toCharArray ( ) ) { s . add ( c ) ; } return s . size ( ) == str . length ( ) ; } public static void main ( String [ ] args ) { String str = " geeksforgeeks " ; if ( ifAllDistinct ( str ) ) System . out . print ( - 1 + "NEW_LINE"); else System . out . print ( findMinLength ( str . toCharArray ( ) ) ) ; } }