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
let MAX = 256 ; let freq ; function preCalculate ( str , n ) { freq [ str [ 0 ] . charCodeAt ( 0 ) ] [ 0 ] = 1 ; for ( let i = 1 ; i < n ; i ++ ) { let ch = str [ i ] ; for ( let j = 0 ; j < MAX ; j ++ ) { let charToUpdate = String . fromCharCode ( 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 ) { if ( l == 0 ) return freq [ ch . charCodeAt ( 0 ) ] [ r ] ; else return ( freq [ ch . charCodeAt ( 0 ) ] [ r ] - freq [ ch . charCodeAt ( 0 ) ] [ l - 1 ] ) ; } function lastNonRepeating ( str , n , l , r ) { for ( let i = r ; i >= l ; i -- ) { let ch = str [ i ] ; if ( getFrequency ( ch , l , r ) == 1 ) return ( " " + ch ) ; } return " " ; } let str = " " ; let n = str . length ; let queries = [ [ 2 , 9 ] , [ 2 , 3 ] , [ 0 , 12 ] ] ; let q = queries . length ; freq = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { freq [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { freq [ i ] [ j ] = 0 ; } } preCalculate ( str , n ) ; for ( let i = 0 ; i < q ; i ++ ) { document . write ( lastNonRepeating ( str , n , queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) + " " ) ; }