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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( string & str , int mid , char a ) { int n = str . size ( ) ; 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 ; } bool possible ( string & str , int mid ) { for ( int i = 0 ; i < 26 ; ++ i ) { if ( check ( str , mid , i + ' a ' ) ) return true ; } return false ; } int findMinLength ( string & 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 ; } bool ifAllDistinct ( string str ) { set < char > s ; for ( char c : str ) { s . insert ( c ) ; } return s . size ( ) == str . size ( ) ; } int main ( ) { string str = " geeksforgeeks " ; if ( ifAllDistinct ( str ) ) cout << -1 << endl ; else cout << findMinLength ( str ) ; return 0 ; }