Minimize length of Substrings containing at least one common Character | C # 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
using System ; using System . Collections . Generic ; class GFG { static bool 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 bool 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 bool ifAllDistinct ( String str ) { HashSet < char > s = new HashSet < char > ( ) ; foreach ( char c in str . ToCharArray ( ) ) { s . Add ( c ) ; } return s . Count == str . Length ; } public static void Main ( String [ ] args ) { String str = " geeksforgeeks " ; if ( ifAllDistinct ( str ) ) Console . Write ( - 1 + " STRNEWLINE " ) ; else Console . Write ( findMinLength ( str . ToCharArray ( ) ) ) ; } }