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 first 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[] = {{0, 3}, {2, 3}, {5, 12}}
Output:
G
e
F
Sub-string for the queries are “Geek”, “ek” and “ForGeeks” and their first non-repeating characters are ‘G’, ‘e’ and ‘F’ respectively.Input: str = “xxyyxx”, q[] = {{2, 3}, {3, 4}}
Output:
-1
y
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 first 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#define MAX 256// To store the frequency of the charactersint freq[MAX][MAX];// Function to pre-calculate the frequency arrayvoid 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 = 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]);}// Function to return the first// non-repeating character in range[l..r]string firstNonRepeating(string str, int n, int l, int r){ char t[2] = ""; // Starting from the first character for (int i = l; i < r; 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) { t[0] = ch; return t; } } // All the characters of the // sub-string are repeating return "-1";}// Driver codeint main(){ string str = "GeeksForGeeks"; int n = str.length(); int queries[][2] = {{0, 3}, {2, 3}, {5, 12}}; int q = sizeof(queries) / sizeof(queries[0]); // Pre-calculate the frequency array freq[MAX][n] = {0}; preCalculate(str, n); for (int i = 0; i < q; i++) cout << firstNonRepeating(str, n, queries[i][0], queries[i][1]) << endl; return 0;}// This code is contributed by// sanjeev2552 |
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 first non-repeating character in range[l..r] static String firstNonRepeating(String str, int n, int l, int r) { // Starting from the first character for (int i = l; i < r; 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[][] = { { 0, 3 }, { 2, 3 }, { 5, 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(firstNonRepeating(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(MAX)] for j in range(MAX)]# 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 first# non-repeating character in range[l..r]def firstNonRepeating(string, n, l, r): t = [""] * 2 # Starting from the first character for i in range(l, r): # Current character ch = string[i] # If frequency of the current character is 1 # then return the character if getFrequency(ch, l, r) == 1: t[0] = ch return t[0] # All the characters of the # sub-string are repeating return "-1"# Driver Codeif __name__ == "__main__": string = "GeeksForGeeks" n = len(string) queries = [(0, 3), (2, 3), (5, 12)] q = len(queries) # Pre-calculate the frequency array preCalculate(string, n) for i in range(q): print(firstNonRepeating(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 first non-repeating character in range[l..r] static string firstNonRepeating(string str, int n, int l, int r) { // Starting from the first character for (int i = l; i < r; 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 = { { 0, 3 }, { 2, 3 }, { 5, 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(firstNonRepeating(str, n, queries[i,0], queries[i,1])); } } } // This code is contributed by AnkitRai01 |
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] = 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()][r]; else return (freq[ch.charCodeAt()][r] - freq[ch.charCodeAt()][l - 1]); } // Function to return the first non-repeating character in range[l..r] function firstNonRepeating(str, n, l, r) { // Starting from the first character for (let i = l; i < r; 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"; } let str = "GeeksForGeeks"; let n = str.length; let queries = [ [ 0, 3 ], [ 2, 3 ], [ 5, 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(firstNonRepeating(str, n, queries[i][0], queries[i][1]) + "</br>"); } </script> |
Output:
G e F
Time Complexity: O(Q * N * MAX), where Q is the number of queries, N is the length of the string and MAX is the number of possible distinct characters.
Space Complexity: O(N * MAX), where N is the length of the string and MAX is the number of possible distinct characters.
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!
