Smallest substring with each letter occurring both in uppercase and lowercase | python 3 program for the above approach ; Function to check if the current string is balanced or not ; For every character , check if there exists uppercase as well as lowercase characters ; Function to find smallest length substring in the given string which is balanced ; Store frequency of lowercase characters ; Stores frequency of uppercase characters ; Count frequency of characters ; Mark those characters which are not present in both lowercase and uppercase ; Initialize the frequencies back to 0 ; Marks the start and end of current substring ; Marks the start and end of required substring ; Stores the length of smallest balanced substring ; Remove all characters obtained so far ; Remove extra characters from front of the current substring ; If substring ( st , i ) is balanced ; No balanced substring ; Store answer string ; Driver Code ; Given string
import sys NEW_LINE def balanced ( small , caps ) : NEW_LINE INDENT for i in range ( 26 ) : NEW_LINE INDENT if ( small [ i ] != 0 and ( caps [ i ] == 0 ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( ( small [ i ] == 0 ) and ( caps [ i ] != 0 ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT return 1 NEW_LINE DEDENT def smallestBalancedSubstring ( s ) : NEW_LINE INDENT small = [ 0 for i in range ( 26 ) ] NEW_LINE caps = [ 0 for i in range ( 26 ) ] NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT if ( ord ( s [ i ] ) >= 65 and ord ( s [ i ] ) <= 90 ) : NEW_LINE INDENT caps [ ord ( s [ i ] ) - 65 ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT small [ ord ( s [ i ] ) - 97 ] += 1 NEW_LINE DEDENT DEDENT mp = { } NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT if ( small [ i ] and caps [ i ] == 0 ) : NEW_LINE INDENT mp [ chr ( i + 97 ) ] = 1 NEW_LINE DEDENT elif ( caps [ i ] and small [ i ] == 0 ) : NEW_LINE INDENT mp [ chr ( i + 65 ) ] = 1 NEW_LINE DEDENT DEDENT for i in range ( len ( small ) ) : NEW_LINE INDENT small [ i ] = 0 NEW_LINE caps [ i ] = 0 NEW_LINE DEDENT i = 0 NEW_LINE st = 0 NEW_LINE start = - 1 NEW_LINE end = - 1 NEW_LINE minm = sys . maxsize NEW_LINE while ( i < len ( s ) ) : NEW_LINE INDENT if ( s [ i ] in mp ) : NEW_LINE INDENT while ( st < i ) : NEW_LINE INDENT if ( ord ( s [ st ] ) >= 65 and ord ( s [ st ] ) <= 90 ) : NEW_LINE INDENT caps [ ord ( s [ st ] ) - 65 ] -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT small [ ord ( s [ st ] ) - 97 ] -= 1 NEW_LINE DEDENT st += 1 NEW_LINE DEDENT i += 1 NEW_LINE st = i NEW_LINE DEDENT else : NEW_LINE INDENT if ( ord ( s [ i ] ) >= 65 and ord ( s [ i ] ) <= 90 ) : NEW_LINE INDENT caps [ ord ( s [ i ] ) - 65 ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT small [ ord ( s [ i ] ) - 97 ] += 1 NEW_LINE DEDENT while ( 1 ) : NEW_LINE INDENT if ( ord ( s [ st ] ) >= 65 and ord ( s [ st ] ) <= 90 and caps [ ord ( s [ st ] ) - 65 ] > 1 ) : NEW_LINE INDENT caps [ ord ( s [ st ] ) - 65 ] -= 1 NEW_LINE st += 1 NEW_LINE DEDENT elif ( ord ( s [ st ] ) >= 97 and ord ( s [ st ] ) <= 122 and small [ ord ( s [ st ] ) - 97 ] > 1 ) : NEW_LINE INDENT small [ ord ( s [ st ] ) - 97 ] -= 1 NEW_LINE st += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( balanced ( small , caps ) ) : NEW_LINE INDENT if ( minm > ( i - st + 1 ) ) : NEW_LINE INDENT minm = i - st + 1 NEW_LINE start = st NEW_LINE end = i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT if ( start == - 1 or end == - 1 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = " " NEW_LINE for i in range ( start , end + 1 , 1 ) : NEW_LINE INDENT ans += s [ i ] NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = " azABaabba " NEW_LINE smallestBalancedSubstring ( s ) NEW_LINE DEDENT