Given a string str, the task is to find the last non-repeating character in it.
For example, if the input string is “GeeksForGeeks”, then the output should be ‘r’ and if the input string is “GeeksQuiz” then the output should be ‘z’. if there is no non-repeating character then print -1.
Examples:
Input: str = “GeeksForGeeks”
Output: r
‘r’ is the first character from the end which has frequency 1.
Input: str = “aabbcc”
Output: -1
All the characters of the given string have frequencies greater than 1.
Approach: Create a frequency array that will store the frequency of each of the characters of the given string. Once the frequencies have been updated, start traversing the string from the end character by character and for every character, if the frequency of the current character is 1 then this is the last non-repeating character. If all the characters have a 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 possibleconst int MAX = 256;// Function to return the last non-repeating characterstatic string lastNonRepeating(string str, int n){ // To store the frequency of each of // the character of the given string int freq[MAX] = {0}; // Update the frequencies for (int i = 0; i < n; i++) freq[str.at(i)]++; // Starting from the last character for (int i = n - 1; i >= 0; i--) { // Current character char ch = str.at(i); // If frequency of the current character is 1 // then return the character if (freq[ch] == 1) { string res; res+=ch; return res; } } // All the characters of the // string are repeating return "-1";}// Driver codeint main() { string str = "GeeksForGeeks"; int n = str.size(); cout<< lastNonRepeating(str, n); return 0;}// This code has been contributed by 29AjayKumar |
Java
// Java implementation of the approachpublic class GFG { // Maximum distinct characters possible static final int MAX = 256; // Function to return the last non-repeating character static String lastNonRepeating(String str, int n) { // To store the frequency of each of // the character of the given string int freq[] = new int[MAX]; // Update the frequencies for (int i = 0; i < n; i++) freq[str.charAt(i)]++; // Starting from the last character for (int i = n - 1; i >= 0; i--) { // Current character char ch = str.charAt(i); // If frequency of the current character is 1 // then return the character if (freq[ch] == 1) return ("" + ch); } // All the characters of the // string are repeating return "-1"; } // Driver code public static void main(String[] args) { String str = "GeeksForGeeks"; int n = str.length(); System.out.println(lastNonRepeating(str, n)); }} |
Python3
# Python3 implementation of the approach # Maximum distinct characters possible MAX = 256; # Function to return the last non-repeating character def lastNonRepeating(string, n) : # To store the frequency of each of # the character of the given string freq = [0]*MAX; # Update the frequencies for i in range(n) : freq[ord(string[i])] += 1; # Starting from the last character for i in range(n-1,-1,-1) : # Current character ch = string[i]; # If frequency of the current character is 1 # then return the character if (freq[ord(ch)] == 1) : return ("" + ch); # All the characters of the # string are repeating return "-1"; # Driver code if __name__ == "__main__" : string = "GeeksForGeeks"; n = len(string); print(lastNonRepeating(string, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG { // Maximum distinct characters possible static readonly int MAX = 256; // Function to return the last non-repeating character static String lastNonRepeating(String str, int n) { // To store the frequency of each of // the character of the given string int []freq = new int[MAX]; // Update the frequencies for (int i = 0; i < n; i++) freq[str[i]]++; // Starting from the last character for (int i = n - 1; i >= 0; i--) { // Current character char ch = str[i]; // If frequency of the current character is 1 // then return the character if (freq[ch] == 1) return ("" + ch); } // All the characters of the // string are repeating return "-1"; } // Driver code public static void Main(String[] args) { String str = "GeeksForGeeks"; int n = str.Length; Console.WriteLine(lastNonRepeating(str, n)); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
function lastNonRepeating(str, n) { // Maximum distinct characters possible const MAX = 256; // To store the frequency of each of // the character of the given string const freq = new Array(MAX).fill(0); // Update the frequencies for (let i = 0; i < n; i++) freq[str.charCodeAt(i)]++; // Starting from the last character for (let i = n - 1; i >= 0; i--) { // Current character const ch = str.charAt(i); // If frequency of the current character is 1 // then return the character if (freq[ch.charCodeAt()] == 1) return ch; } // All the characters of the // string are repeating return "-1";}const str = "GeeksForGeeks";const n = str.length;console.log(lastNonRepeating(str, n)); |
Output:
r
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(256) ? O(1), no extra space is required, so it is a constant.
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!
