Given a string str which consists of only lowercase letters and an array arr[][] that represents range queries on the given string str where each query contains 3 integers, {L, R, N} such that for each query we have to output the Nth smallest character in the given range [L, R] as specified in the query.
Examples:
Input: str = “afbccdeb”, arr[][] = {{2, 4, 1}, {1, 6, 4}, {1, 8, 7}}
Output: b c e
Explanation:
1st smallest character in range [2, 4] or in the sub-string “fbc” is ‘b’
4th smallest character in range [1, 6] or in the sub-string “afbccd” is ‘c’
7th smallest character in range [1, 8] or in the whole string is ‘e’
Input: str = “neveropen”, arr[][] = {{1, 4, 2}, {3, 7, 3}, {4, 13, 4}}
Output: e k g
Explanation:
2nd smallest character in range [1, 4] or in the sub-string “geek” is ‘e’
3rd smallest character in range [3, 7] or in the sub-string “eksfo” is ‘k’
4th smallest character in range [4, 13] or in the sub-string “sforneveropen”is ‘g’
Naive Approach: A naive approach is to run a loop from L to R and generate a substring in this range. Once the substring is found, sort the substring to find Nth character in the sorted string.
Time Complexity Analysis:
- In the worst case, traversing from L to R will have a complexity of O(N).
- Sorting a substring takes a complexity of O(N * Log(N)).
- Since we are sorting the substring for every query, therefore, the overall time complexity is O(N2 * Log(N)).
Efficient Approach: The idea is to make use of a two-dimensional hash table. The hash table H[][] is initialized for N rows and 26 columns where N represents the length of the string and 26 as there are a total of 26 lowercase letters.
The idea behind hashtable is that for each index i where ‘i’ ranges from 1 to N, we keep a track of the number of occurrence of each of the 26 lowercase letters on or before the ith index. To do this, hashing is used where each character is treated as a number in the following way:
'a' -> 0 'b' -> 1 . . . 'z' -> 25
Therefore, for each query {L, R, N}, we get the occurrence of each character for the given range by subtracting the elements of H[L – 1][j] from H[R][j] where j ranges from 0 to 25 in the form of a hash table. After this, all we need to do is traverse from 0 to 25 and add the contents of the resultant array. Whenever the sum is equal to or exceeds N, the character representing that index is the required answer.
For example, if on 5th index(j = 4), the sum till then exceeds N, the answer becomes ‘e’ as 4 is equivalent to the character ‘e’. Below is the pictorial representation of the sample case:
The image describes the hashtable corresponding to the given string. For range [2, 4], we perform subtraction of the contents from H[2 – 1] from H[4]. We get:
Clearly this resultant array contains the count of elements that are within the range [2, 4]. So we simply traverse from 0 to 25 and count the contents until we reach N. In the query for N = 1 the answer is ‘b’, for N = 2 the answer becomes ‘c’ and so on.
Below is the implementation of the above approach:
C++
// C++ implementation to find the Nth// smallest character in a given range// of a string#include <bits/stdc++.h>using namespace std;// Query structure to represent a query range// along with nstruct Query { int l, r, n;};// Function to print the Nth smallest// character for a given range in a stringint findSmallest(string s, Query q[], int m){ // Integer N contains the // length of the string s int N = s.length(); // We initialise our hash array and // set all the elements to 0 int H[N + 1][26]; memset(H, 0, sizeof(H)); // We preprocess our string in which we // update the current character // as well as add the H[i - 1]th // array to H[i] for (int i = 1; i <= N; i++) { // Incrementing the frequency of // ith row based on the occurrence // of the characters up to i-th index ++H[i][s[i - 1] - 'a']; // Adding the values of the array at // the previous index to the next index for (int j = 0; j < 26; j++) { H[i][j] += H[i - 1][j]; } } // We traverse from 0 to m to // fetch all the queries for (int j = 0; j < m; j++) { // Extracting L, R and N // from the query array q int l = q[j].l, r = q[j].r, n = q[j].n; // The initial sum is set to 0 int sum = 0; // We subtract H[l-1] from h[r] // and add it to the sum for (int i = 0; i < 26; i++) { sum += H[r][i] - H[l - 1][i]; // Whenever the sum is greater than // or equal to N, the equivalent // character of the index is our // nth smallest character if (sum >= n) { cout << (char)('a' + i) << "\n"; break; } } }}// Driver codeint main(){ // Input string s string s = "afbccdeb"; // Query array q, for each q // it contains l, r and n Query q[] = { { 2, 4, 1 }, { 1, 6, 4 }, { 1, 8, 7 } }; int x = sizeof(q) / sizeof(q[0]); findSmallest(s, q, x);} |
Java
// JAVA implementation to find the Nth// smallest character for a given range// in a stringimport java.io.*;import java.util.*;class GFG { // Query class to represent a query range // along with n public static class Query { public int l, r, n; // Constructor for the Query class which // takes three integers L, R, N public Query(int l, int r, int n) { this.l = l; this.r = r; this.n = n; } } // Function to print the Nth smallest // character for a given range in a string public static void printSmallest(String s, Query[] q) { // Integer N contains the // length of the string s int N = s.length(); // We initialise our hash array and // set all the elements to 0 int[][] H = new int[N + 1][26]; // We preprocess our string in which we // update the current character // as well as add the H[i - 1]th // array to H[i] for (int i = 1; i <= N; i++) { // Incrementing the frequency of // ith row based on the occurrence // of the characters up to i-th index ++H[i][s.charAt(i - 1) - 'a']; // Adding the values of the array at // the previous index to the next index for (int j = 0; j < 26; j++) { H[i][j] += H[i - 1][j]; } } // Integer m contains the // number of queries int m = q.length; // We traverse from 0 to m to // fetch all the queries for (int j = 0; j < m; j++) { // Extracting l, r and n // from the query array q int l = q[j].l, r = q[j].r, n = q[j].n; // The initial sum is set to 0 int sum = 0; // We subtract H[l-1] from h[r] // and add it to the sum for (int i = 0; i < 26; i++) { sum += H[r][i] - H[l - 1][i]; // Whenever the sum is greater than // or equal to N, the equivalent // character of the index is our // nth smallest character if (sum >= n) { System.out.println((char)('a' + i)); break; } } } } // Driver code public static void main(String args[]) { // Input string s String s = "afbccdeb"; // Query array q, for each q // it contains l, r and n Query[] q = { new Query(2, 4, 1), new Query(1, 6, 4), new Query(1, 8, 7) }; // Calling the function printSmallest(s, q); }} |
Python3
# Python3 implementation to find the Nth# smallest character in a given range# of a string# Function to print the Nth smallest# character for a given range in a stringdef findSmallest(s, q, m): # Integer N contains the # length of the s N = len(s) # We initialise our hash array and # set all the elements to 0 H = [[0 for i in range(26)]for i in range(N + 1)] # We preprocess our in which we # update the current character # as well as add the H[i - 1]th # array to H[i] for i in range(1, N + 1): # Incrementing the frequency of # ith row based on the occurrence # of the characters up to i-th index H[i][ord(s[i - 1]) - ord('a')] += 1 # Adding the values of the array at # the previous index to the next index for j in range(26): H[i][j] += H[i - 1][j] # We traverse from 0 to m to # fetch all the queries for j in range(m): # Extracting L, R and N # from the query array q l = q[j][0] r = q[j][1] n = q[j][2] # The initial sum is set to 0 sum = 0 # We subtract H[l-1] from h[r] # and add it to the sum for i in range(26): sum += H[r][i] - H[l - 1][i] # Whenever the sum is greater than # or equal to N, the equivalent # character of the index is our # nth smallest character if (sum >= n): print(chr(ord('a') + i)) break# Driver codeif __name__ == '__main__': # Input s s = "afbccdeb" # Query array q, for each q # it contains l, r and n q = [ [ 2, 4, 1 ], [ 1, 6, 4 ], [ 1, 8, 7 ] ] x = len(q) findSmallest(s, q, x) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the Nth// smallest character for a given range// in a stringusing System;class GFG { // Query class to represent a query range // along with n public class Query { public int l, r, n; // Constructor for the Query class which // takes three integers L, R, N public Query(int l, int r, int n) { this.l = l; this.r = r; this.n = n; } } // Function to print the Nth smallest // character for a given range in a string public static void printSmallest(String s, Query[] q) { // int N contains the // length of the string s int N = s.Length; // We initialise our hash array and // set all the elements to 0 int[,] H = new int[N + 1,26]; // We preprocess our string in which we // update the current character // as well as add the H[i - 1]th // array to H[i] for (int i = 1; i <= N; i++) { // Incrementing the frequency of // ith row based on the occurrence // of the characters up to i-th index ++H[i, s[i - 1] - 'a']; // Adding the values of the array at // the previous index to the next index for (int j = 0; j < 26; j++) { H[i, j] += H[i - 1, j]; } } // int m contains the // number of queries int m = q.Length; // We traverse from 0 to m to // fetch all the queries for (int j = 0; j < m; j++) { // Extracting l, r and n // from the query array q int l = q[j].l, r = q[j].r, n = q[j].n; // The initial sum is set to 0 int sum = 0; // We subtract H[l-1] from h[r] // and add it to the sum for (int i = 0; i < 26; i++) { sum += H[r, i] - H[l - 1, i]; // Whenever the sum is greater than // or equal to N, the equivalent // character of the index is our // nth smallest character if (sum >= n) { Console.WriteLine((char)('a' + i)); break; } } } } // Driver code public static void Main(String []args) { // Input string s String s = "afbccdeb"; // Query array q, for each q // it contains l, r and n Query[] q = { new Query(2, 4, 1), new Query(1, 6, 4), new Query(1, 8, 7) }; // Calling the function printSmallest(s, q); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JAVAscript implementation to find the Nth// smallest character for a given range// in a string// Query class to represent a query range // along with nclass Query{ // Constructor for the Query class which // takes three integers L, R, N constructor(l,r,n) { this.l = l; this.r = r; this.n = n; }}// Function to print the Nth smallest // character for a given range in a stringfunction printSmallest(s,q){ // Integer N contains the // length of the string s let N = s.length; // We initialise our hash array and // set all the elements to 0 let H = new Array(N + 1); for(let i = 0; i < N + 1; i++) { H[i] = new Array(26); for(let j = 0; j < 26; j++) { H[i][j] = 0; } } // We preprocess our string in which we // update the current character // as well as add the H[i - 1]th // array to H[i] for (let i = 1; i <N; i++) { // Incrementing the frequency of // ith row based on the occurrence // of the characters up to i-th index ++H[i][s[i].charCodeAt(0) - 'a'.charCodeAt(0)]; // Adding the values of the array at // the previous index to the next index for (let j = 0; j < 26; j++) { H[i][j] += H[i - 1][j]; } } // Integer m contains the // number of queries let m = q.length; // We traverse from 0 to m to // fetch all the queries for (let j = 0; j < m; j++) { // Extracting l, r and n // from the query array q let l = q[j].l, r = q[j].r, n = q[j].n; // The initial sum is set to 0 let sum = 0; // We subtract H[l-1] from h[r] // and add it to the sum for (let i = 0; i < 26; i++) { sum += H[r][i] - H[l - 1][i]; // Whenever the sum is greater than // or equal to N, the equivalent // character of the index is our // nth smallest character if (sum >= n) { document.write(String.fromCharCode('a'.charCodeAt(0) + i)+"<br>"); break; } } }}// Driver codelet s = "afbccdeb";let q = [ new Query(2, 4, 1), new Query(1, 6, 4), new Query(1, 8, 7) ]; // Calling the functionprintSmallest(s, q);// This code is contributed by unknown2108</script> |
b c e
Time Complexity Analysis:
- For the above approach, though the preprocessing consists of two loops, the second loop runs for a constant number of times(26). Therefore, the time taken for preprocessing is O(N).
- After preprocessing, for every query, the character is returned in constant time as again here the for loop runs a constant number of times(26). Therefore, the time taken for answering each query is O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
