Length of the largest substring which have character with frequency greater than or equal to half of the substring | 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 can be used for other characters . ; Driver Code
function maxLength ( s , n ) { var ans = - 2147483648 ; var A = [ ] ; var L = [ ] ; var R = [ ] ; var freq = new Array ( n + 5 ) . fill ( 0 ) ; for ( var i = 0 ; i < 26 ; i ++ ) { var count = 0 ; for ( var j = 0 ; j < n ; j ++ ) { if ( s [ j ] . charCodeAt ( 0 ) - " " . charCodeAt ( 0 ) === i ) count ++ ; freq [ j ] = count ; } for ( var j = 1 ; j < n ; j ++ ) { L . push ( 2 * freq [ j - 1 ] - j ) ; R . push ( 2 * freq [ j ] - j ) ; } var max_len = - 2147483648 ; var min_val = 2147483648 ; for ( var j = 0 ; j < L . length ; j ++ ) { min_val = Math . min ( min_val , L [ j ] ) ; A . push ( min_val ) ; var l = 0 , r = j ; while ( l <= r ) { var mid = ( l + r ) >> 1 ; if ( A [ mid ] <= R [ j ] ) { max_len = Math . max ( max_len , j - mid + 1 ) ; r = mid - 1 ; } else { l = mid + 1 ; } } } ans = Math . max ( ans , max_len ) ; A = [ ] ; R = [ ] ; L = [ ] ; } return ans ; } var s = " " ; var n = s . length ; document . write ( maxLength ( s , n ) ) ;