Queries to find the first non | Maximum distinct characters possible ; To store the frequency of the characters ; Function to pre - calculate the frequency array ; Only the first character has frequency 1 till index 0 ; Starting from the second character of the string ; For every possible character ; Current character under consideration ; If it is equal to the character at the current index ; Function to return the frequency of the given character in the sub - string str [ l ... r ] ; Function to return the first non - repeating character in range [ l . . r ] ; Starting from the first character ; Current character ; If frequency of the current character is 1 then return the character ; All the characters of the sub - string are repeating ; Driver Code ; Pre - calculate the frequency array
MAX = 256 NEW_LINE freq = [ [ 0 for i in range ( MAX ) ] for j in range ( MAX ) ] NEW_LINE def preCalculate ( string , n ) : NEW_LINE INDENT freq [ ord ( string [ 0 ] ) ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT ch = string [ i ] NEW_LINE for j in range ( MAX ) : NEW_LINE INDENT charToUpdate = chr ( j ) NEW_LINE if charToUpdate == ch : NEW_LINE INDENT freq [ j ] [ i ] = freq [ j ] [ i - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT freq [ j ] [ i ] = freq [ j ] [ i - 1 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def getFrequency ( ch , l , r ) : NEW_LINE INDENT if l == 0 : NEW_LINE INDENT return freq [ ord ( ch ) ] [ r ] NEW_LINE DEDENT else : NEW_LINE INDENT return ( freq [ ord ( ch ) ] [ r ] - freq [ ord ( ch ) ] [ l - 1 ] ) NEW_LINE DEDENT DEDENT def firstNonRepeating ( string , n , l , r ) : NEW_LINE INDENT t = [ " " ] * 2 NEW_LINE for i in range ( l , r ) : NEW_LINE INDENT ch = string [ i ] NEW_LINE if getFrequency ( ch , l , r ) == 1 : NEW_LINE INDENT t [ 0 ] = ch NEW_LINE return t [ 0 ] NEW_LINE DEDENT DEDENT return " - 1" NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " GeeksForGeeks " NEW_LINE n = len ( string ) NEW_LINE queries = [ ( 0 , 3 ) , ( 2 , 3 ) , ( 5 , 12 ) ] NEW_LINE q = len ( queries ) NEW_LINE preCalculate ( string , n ) NEW_LINE for i in range ( q ) : NEW_LINE INDENT print ( firstNonRepeating ( string , n , queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) ) NEW_LINE DEDENT DEDENT