Given a string str, the task is to answer Q queries where every query consists of two integers L and R and we have to find the last non-repeating character in the sub-string str[L…R]. If there is no non-repeating character then print -1.
Examples:
Input: str = “GeeksForGeeks”, q[] = {{2, 9}, {2, 3}, {0, 12}}
Output:
G
k
r
Sub-string for the queries are “eksForGe”, “ek” and “GeeksForGeeks” and their last non-repeating characters are ‘G’, ‘k’ and ‘r’ respectively.
‘G’ is the first character from the end in given range which has frequency 1.
Input: str = “xxyyxx”, q[] = {{2, 3}, {3, 4}}
Output:
-1
x
Approach: Create a frequency array freq[][] where freq[i][j] stores the frequency of the character in the sub-string str[0…j] whose ASCII value is i. Now, frequency of any character in the sub-string str[i…j] whose ASCII value is x can be calculated as freq[x][j] = freq[x][i – 1].
Now for every query, start traversing the string in the given range i.e. str[L…R] and for every character, if its frequency is 1 then this is the last non-repeating character in the required sub-string. If all the characters have frequency greater than 1 then print -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h>using namespace std;// Maximum distinct characters possible int MAX = 256; // To store the frequency of the characters int freq[256][1000] = {0}; // Function to pre-calculate the frequency array void preCalculate(string str, int n) { // Only the first character has // frequency 1 till index 0 freq[(int)str[0]][0] = 1; // Starting from the second // character of the string for (int i = 1; i < n; i++) { char ch = str[i]; // For every possible character for (int j = 0; j < MAX; j++) { // Current character under consideration char charToUpdate = (char)j; // If it is equal to the character // at the current index if (charToUpdate == ch) freq[j][i] = freq[j][i - 1] + 1; else freq[j][i] = freq[j][i - 1]; } } } // Function to return the frequency of the // given character in the sub-string str[l...r] 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 class has a constructor // that allows us to specify size of // string as first parameter and character // to be filled in given size as second // parameter. string s(1, x); return s; }// Function to return the last non-repeating character string lastNonRepeating(string str, int n, int l, int r) { // Starting from the last character for (int i = r; i >= l; i--) { // Current character char ch = str[i]; // If frequency of the current character is 1 // then return the character if (getFrequency(ch, l, r) == 1) return getString(ch); } // All the characters of the // sub-string are repeating return "-1"; } // Driver code int main(){ string str = "GeeksForGeeks"; int n = str.length(); int queries[3][2] = { { 2, 9 }, { 2, 3 }, { 0, 12 } }; int q =3; // Pre-calculate the frequency array preCalculate(str, n); for (int i = 0; i < q; i++) { cout << (lastNonRepeating(str, n, queries[i][0], queries[i][1]))<<endl;; } } // This code is contributed by Arnab Kundu |
Java
// Java implementation of the approachpublic class GFG { // Maximum distinct characters possible static final int MAX = 256; // To store the frequency of the characters static int freq[][]; // Function to pre-calculate the frequency array static void preCalculate(String str, int n) { // Only the first character has // frequency 1 till index 0 freq[(int)str.charAt(0)][0] = 1; // Starting from the second // character of the string for (int i = 1; i < n; i++) { char ch = str.charAt(i); // For every possible character for (int j = 0; j < MAX; j++) { // Current character under consideration char charToUpdate = (char)j; // If it is equal to the character // at the current index if (charToUpdate == ch) freq[j][i] = freq[j][i - 1] + 1; else freq[j][i] = freq[j][i - 1]; } } } // Function to return the frequency of the // given character in the sub-string str[l...r] static 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]); } // Function to return the last non-repeating character static String lastNonRepeating(String str, int n, int l, int r) { // Starting from the last character for (int i = r; i >= l; i--) { // Current character char ch = str.charAt(i); // If frequency of the current character is 1 // then return the character if (getFrequency(ch, l, r) == 1) return ("" + ch); } // All the characters of the // sub-string are repeating return "-1"; } // Driver code public static void main(String[] args) { String str = "GeeksForGeeks"; int n = str.length(); int queries[][] = { { 2, 9 }, { 2, 3 }, { 0, 12 } }; int q = queries.length; // Pre-calculate the frequency array freq = new int[MAX][n]; preCalculate(str, n); for (int i = 0; i < q; i++) { System.out.println(lastNonRepeating(str, n, queries[i][0], queries[i][1])); } }} |
Python3
# Python3 implementation of the approach# Maximum distinct characters possibleMAX = 256# To store the frequency of the charactersfreq = [[0 for i in range(256)] for j in range(1000)]# Function to pre-calculate# the frequency arraydef preCalculate(string, n): # Only the first character has # frequency 1 till index 0 freq[ord(string[0])][0] = 1 # Starting from the second # character of the string for i in range(1, n): ch = string[i] # For every possible character for j in range(MAX): # Current character under consideration charToUpdate = chr(j) # If it is equal to the character # at the current index if charToUpdate == ch: freq[j][i] = freq[j][i - 1] + 1 else: freq[j][i] = freq[j][i - 1]# Function to return the frequency of the# given character in the sub-string str[l...r]def getFrequency(ch, l, r): if l == 0: return freq[ord(ch)][r] else: return (freq[ord(ch)][r] - freq[ord(ch)][l - 1])# Function to return the # last non-repeating characterdef lastNonRepeating(string, n, l, r): # Starting from the last character for i in range(r, l - 1, -1): # Current character ch = string[i] # If frequency of the current character is 1 # then return the character if getFrequency(ch, l, r) == 1: return ch # All the characters of the # sub-string are repeating return "-1"# Driver Codeif __name__ == "__main__": string = "GeeksForGeeks" n = len(string) queries = [(2, 9), (2, 3), (0, 12)] q = len(queries) # Pre-calculate the frequency array preCalculate(string, n) for i in range(q): print(lastNonRepeating(string, n, queries[i][0], queries[i][1]))# This code is contributed by# sanjeev2552 |
C#
// C# implementation of the approach using System;class GFG { // Maximum distinct characters possible static int MAX = 256; // To store the frequency of the characters static int [,]freq; // Function to pre-calculate the frequency array static void preCalculate(string str, int n) { // Only the first character has // frequency 1 till index 0 freq[(int)str[0],0] = 1; // Starting from the second // character of the string for (int i = 1; i < n; i++) { char ch = str[i]; // For every possible character for (int j = 0; j < MAX; j++) { // Current character under consideration char charToUpdate = (char)j; // If it is equal to the character // at the current index if (charToUpdate == ch) freq[j, i] = freq[j, i - 1] + 1; else freq[j, i] = freq[j, i - 1]; } } } // Function to return the frequency of the // given character in the sub-string str[l...r] static 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]); } // Function to return the last non-repeating character static String lastNonRepeating(string str, int n, int l, int r) { // Starting from the last character for (int i = r; i >= l; i--) { // Current character char ch = str[i]; // If frequency of the current character is 1 // then return the character if (getFrequency(ch, l, r) == 1) return ("" + ch); } // All the characters of the // sub-string are repeating return "-1"; } // Driver code public static void Main() { string str = "GeeksForGeeks"; int n = str.Length; int [,]queries = { { 2, 9 }, { 2, 3 }, { 0, 12 } }; int q = queries.Length; // Pre-calculate the frequency array freq = new int[MAX,n]; preCalculate(str, n); for (int i = 0; i < q; i++) { Console.WriteLine(lastNonRepeating(str, n, queries[i,0], queries[i,1])); } } } // This code is contributed by AnkitRai01 |
PHP
<?php// PHP implementation of the approach // Maximum distinct characters possible $MAX = 256; // To store the frequency of the characters $freq = array_fill(0, 256, array_fill(0, 1000, 0)); // Function to pre-calculate the frequency array function preCalculate($str, $n) { global $freq; global $MAX; // Only the first character has // frequency 1 till index 0 $freq[ord($str[0])][0] = 1; // Starting from the second // character of the string for ($i = 1; $i < $n; $i++) { $ch = $str[$i]; // For every possible character for ($j = 0; $j < $MAX; $j++) { // Current character under consideration $charToUpdate = chr($j); // If it is equal to the character // at the current index if ($charToUpdate == $ch) $freq[$j][$i] = $freq[$j][$i - 1] + 1; else $freq[$j][$i] = $freq[$j][$i - 1]; } } } // Function to return the frequency of the // given character in the sub-string $str[$l...$r] 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 to return the last non-repeating character function lastNonRepeating($str, $n, $l, $r) { // Starting from the last character for ($i = $r; $i >= $l; $i--) { // Current character $ch = $str[$i]; // If frequency of the current character is 1 // then return the character if (getFrequency($ch, $l, $r) == 1) return $ch; } // All the characters of the // sub-string are repeating return "-1"; } // Driver code $str = "GeeksForGeeks"; $n = strlen($str); $queries = array( array( 2, 9 ), array( 2, 3 ), array( 0, 12 ) );$q =3; // Pre-calculate the frequency array preCalculate($str, $n); for ($i = 0; $i < $q; $i++) { echo (lastNonRepeating($str, $n, $queries[$i][0], $queries[$i][1])), "\n"; } // This code is contributed by ihritik?> |
Javascript
<script>// JavaScript implementation of the approach// Maximum distinct characters possible let MAX = 256; // To store the frequency of the characters let freq; // Function to pre-calculate the frequency array function preCalculate(str,n) { // Only the first character has // frequency 1 till index 0 freq[str[0].charCodeAt(0)][0] = 1; // Starting from the second // character of the string for (let i = 1; i < n; i++) { let ch = str[i]; // For every possible character for (let j = 0; j < MAX; j++) { // Current character under consideration let charToUpdate = String.fromCharCode(j); // If it is equal to the character // at the current index if (charToUpdate == ch) freq[j][i] = freq[j][i - 1] + 1; else freq[j][i] = freq[j][i - 1]; } } } // Function to return the frequency of the // given character in the sub-string str[l...r] 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 to return the last non-repeating character function lastNonRepeating(str,n,l,r) { // Starting from the last character for (let i = r; i >= l; i--) { // Current character let ch = str[i]; // If frequency of the current character is 1 // then return the character if (getFrequency(ch, l, r) == 1) return ("" + ch); } // All the characters of the // sub-string are repeating return "-1"; } // Driver code let str = "GeeksForGeeks"; let n = str.length; let queries = [[ 2, 9 ], [ 2, 3 ], [ 0, 12 ]]; let q = queries.length; // Pre-calculate the frequency array 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])+ "<br>");}// This code is contributed by rag2127</script> |
Output:
G k r
Time Complexity: O(256*N), as we are using nested loops for traversing 256*N times. Where N is the length of the string.
Auxiliary Space: O(256*1000), as we are using extra space for the frequency map.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
