Queries to find the last 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 last non - repeating character ; Starting from the last 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
< ? php $ MAX = 256 ; $ freq = array_fill ( 0 , 256 , array_fill ( 0 , 1000 , 0 ) ) ; function preCalculate ( $ str , $ n ) { global $ freq ; global $ MAX ; $ freq [ ord ( $ str [ 0 ] ) ] [ 0 ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ ch = $ str [ $ i ] ; for ( $ j = 0 ; $ j < $ MAX ; $ j ++ ) { $ charToUpdate = chr ( $ j ) ; if ( $ charToUpdate == $ ch ) $ freq [ $ j ] [ $ i ] = $ freq [ $ j ] [ $ i - 1 ] + 1 ; else $ freq [ $ j ] [ $ i ] = $ freq [ $ j ] [ $ i - 1 ] ; } } } function getFrequency ( $ ch , $ l , $ r ) { global $ freq ; if ( $ l == 0 ) return $ freq [ ord ( $ ch ) ] [ $ r ] ; else return ( $ freq [ ord ( $ ch ) ] [ $ r ] - $ freq [ ord ( $ ch ) ] [ $ l - 1 ] ) ; } function lastNonRepeating ( $ str , $ n , $ l , $ r ) { for ( $ i = $ r ; $ i >= $ l ; $ i -- ) { $ ch = $ str [ $ i ] ; if ( getFrequency ( $ ch , $ l , $ r ) == 1 ) return $ ch ; } return " - 1" ; } $ str = " GeeksForGeeks " ; $ n = strlen ( $ str ) ; $ queries = array ( array ( 2 , 9 ) , array ( 2 , 3 ) , array ( 0 , 12 ) ) ; $ q = 3 ; preCalculate ( $ str , $ n ) ; for ( $ i = 0 ; $ i < $ q ; $ i ++ ) { echo ( lastNonRepeating ( $ str , $ n , $ queries [ $ i ] [ 0 ] , $ queries [ $ i ] [ 1 ] ) ) , " STRNEWLINE " ; } ? >