Length of the largest substring which have character with frequency greater than or equal to half of the substring | Python3 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
import sys NEW_LINE def maxLength ( s , n ) : NEW_LINE INDENT ans = - ( sys . maxsize + 1 ) ; NEW_LINE A , L , R = [ ] , [ ] , [ ] ; NEW_LINE freq = [ 0 ] * ( n + 5 ) ; NEW_LINE DEDENT ' NEW_LINE INDENT for i in range ( 26 ) : NEW_LINE INDENT count = 0 ; NEW_LINE for j in range ( n ) : NEW_LINE INDENT if ( ord ( s [ j ] ) - ord ( ' a ' ) == i ) : NEW_LINE INDENT count += 1 ; NEW_LINE DEDENT freq [ j ] = count ; NEW_LINE DEDENT for j in range ( n ) : NEW_LINE INDENT L . append ( ( 2 * freq [ j - 1 ] ) - j ) ; NEW_LINE R . append ( ( 2 * freq [ j ] ) - j ) ; NEW_LINE DEDENT max_len = - ( sys . maxsize + 1 ) ; NEW_LINE min_val = sys . maxsize ; NEW_LINE for j in range ( n ) : NEW_LINE INDENT min_val = min ( min_val , L [ j ] ) ; NEW_LINE A . append ( min_val ) ; NEW_LINE l = 0 ; r = j ; NEW_LINE while ( l <= r ) : NEW_LINE INDENT mid = ( l + r ) >> 1 ; NEW_LINE if ( A [ mid ] <= R [ j ] ) : NEW_LINE INDENT max_len = max ( max_len , j - mid + 1 ) ; NEW_LINE r = mid - 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT l = mid + 1 ; NEW_LINE DEDENT DEDENT DEDENT ans = max ( ans , max_len ) ; NEW_LINE A . clear ( ) ; NEW_LINE R . clear ( ) ; NEW_LINE L . clear ( ) ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " ababbbacbcbcca " ; NEW_LINE n = len ( s ) ; NEW_LINE print ( maxLength ( s , n ) ) ; NEW_LINE DEDENT