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 can be used for other characters . ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int maxLength ( String s , int n ) { int ans = int . MinValue ; List < int > A = new List < int > ( ) ; List < int > L = new List < int > ( ) ; List < int > R = new List < int > ( ) ; int [ ] freq = new int [ n + 5 ] ; for ( int i = 0 ; i < 26 ; i ++ ) { int count = 0 ; for ( int j = 0 ; j < n ; j ++ ) { if ( s [ j ] - ' a ' == i ) count ++ ; freq [ j ] = count ; } for ( int j = 1 ; j < n ; j ++ ) { L . Add ( ( 2 * freq [ j - 1 ] ) - j ) ; R . Add ( ( 2 * freq [ j ] ) - j ) ; } int max_len = int . MinValue ; int min_val = int . MaxValue ; for ( int j = 0 ; j < L . Count ; j ++ ) { min_val = Math . Min ( min_val , L [ j ] ) ; A . Add ( min_val ) ; int l = 0 , r = j ; while ( l <= r ) { int 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 . Clear ( ) ; R . Clear ( ) ; L . Clear ( ) ; } return ans ; } public static void Main ( String [ ] args ) { String s = " ababbbacbcbcca " ; int n = s . Length ; Console . WriteLine ( maxLength ( s , n ) ) ; } }