Length of the largest substring which have character with frequency greater than or equal to half of the substring | C ++ implementation of the above approach ; Function to return the length of the longest sub string having frequency of a character greater than half of the length of the sub string ; for each of the character ' a ' to ' z ' ; finding frequency prefix array of the character ; Finding the r [ ] and l [ ] arrays . ; for each j from 0 to n ; Finding the lower bound of i . ; storing the maximum value of i - j + 1 ; clearing all the vector so that it clearing be use for other character . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxLength ( string s , int n ) { int ans = INT_MIN ; vector < int > A , L , R ; int freq [ n + 5 ] ; for ( int i = 0 ; i < 26 ; i ++ ) { int count = 0 ; memset ( freq , 0 , sizeof freq ) ; for ( int j = 0 ; j < n ; j ++ ) { if ( s [ j ] - ' a ' == i ) count ++ ; freq [ j ] = count ; } for ( int j = 0 ; j < n ; j ++ ) { L . push_back ( ( 2 * freq [ j - 1 ] ) - j ) ; R . push_back ( ( 2 * freq [ j ] ) - j ) ; } int max_len = INT_MIN ; int min_val = INT_MAX ; for ( int j = 0 ; j < n ; j ++ ) { min_val = min ( min_val , L [ j ] ) ; A . push_back ( min_val ) ; int l = 0 , r = j ; while ( l <= r ) { int mid = ( l + r ) >> 1 ; if ( A [ mid ] <= R [ j ] ) { max_len = max ( max_len , j - mid + 1 ) ; r = mid - 1 ; } else { l = mid + 1 ; } } } ans = max ( ans , max_len ) ; A . clear ( ) ; R . clear ( ) ; L . clear ( ) ; } return ans ; } int main ( ) { string s = " ababbbacbcbcca " ; int n = s . length ( ) ; cout << maxLength ( s , n ) << ' ' ; return 0 ; }