Queries to find the last non | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MAX = 256 ; int freq [ 256 ] [ 1000 ] = { 0 } ; void preCalculate ( string str , int n ) { freq [ ( int ) str [ 0 ] ] [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { char ch = str [ i ] ; for ( int j = 0 ; j < MAX ; j ++ ) { char charToUpdate = ( char ) j ; if ( charToUpdate == ch ) freq [ j ] [ i ] = freq [ j ] [ i - 1 ] + 1 ; else freq [ j ] [ i ] = freq [ j ] [ i - 1 ] ; } } } int getFrequency ( char ch , int l , int r ) { if ( l == 0 ) return freq [ ( int ) ch ] [ r ] ; else return ( freq [ ( int ) ch ] [ r ] - freq [ ( int ) ch ] [ l - 1 ] ) ; } string getString ( char x ) { string s ( 1 , x ) ; return s ; } string lastNonRepeating ( string str , int n , int l , int r ) { for ( int i = r ; i >= l ; i -- ) { char ch = str [ i ] ; if ( getFrequency ( ch , l , r ) == 1 ) return getString ( ch ) ; } return " - 1" ; } int main ( ) { string str = " GeeksForGeeks " ; int n = str . length ( ) ; int queries [ 3 ] [ 2 ] = { { 2 , 9 } , { 2 , 3 } , { 0 , 12 } } ; int q = 3 ; preCalculate ( str , n ) ; for ( int i = 0 ; i < q ; i ++ ) { cout << ( lastNonRepeating ( str , n , queries [ i ] [ 0 ] , queries [ i ] [ 1 ] ) ) << endl ; ; } }