Given a string S of size N and an array queries, containing Q queries in the form of L, R. The task is to find the lexicographically smallest anagram of string from L to R for each query.
Example:
Input: S = “bbaacd”
queries[]={{1, 3}, {2, 5}}
Output:
aab
aacdInput: S=”bbdfaaacaed”
queries[]={{0, 4}, {4, 8}}
Output:
abbdf
aaaac
Approach: This question can be solved by precomputing the frequencies of all characters present till ith index in string S, because by doing so, it’s easier as well as time-saving to calculate the frequencies of characters between L to R, in each query. Now, to solve this question, follow the below steps:
- Create a function preComputeFreq, which will store the frequencies of characters in string S, for every index i.
- Create a function named smallestAnagram and run it for each query. In this function:
- Create a string ans, which will store the lexicographically smallest anagram from L to R.
- Find the frequencies, till index R and till index L-1, to get the frequencies between L to R.
- Run a loop from 0 to the frequency of that character and add it to the string ans.
- Return string ans as the answer for each query.
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the frequencies of all// characters till each index in stringvoid preComputeFreq(string& S, vector<vector<int> >& freq){ vector<int> f(26, 0); for (int i = 0; i < S.size(); ++i) { freq[i] = f; freq[i][S[i] - 'a']++; f = freq[i]; }}// Function to get the// smallest anagram from L to Rstring smallestAnagram(string& S, int L, int R, vector<vector<int> >& freq){ string ans; // Finding net frequencies // of character from L to R for (int i = 0; i < 26; i++) { int low = 0; if (L > 0) { low = freq[L - 1][i]; } // Adding characters to string ans for (int j = 0; j < freq[R][i] - low; j++) { ans += (char)('a' + i); } } return ans;}void smallestAnagramUtil(string& S, int N, vector<pair<int, int> >& queries){ vector<vector<int> > freq(N, vector<int>(26, 0)); preComputeFreq(S, freq); for (auto x : queries) { int L = x.first; int R = x.second; cout << smallestAnagram(S, L, R, freq) << endl; }}// Driver Codeint main(){ string S = "bbdfaaacaed"; int N = S.size(); vector<pair<int, int> > queries = { { 0, 4 }, { 4, 8 } }; smallestAnagramUtil(S, N, queries);} |
Java
// Java code for the above approachimport java.util.ArrayList;import java.util.List;public class Main{ // Function to calculate the frequencies of all // characters till each index in string public static void preComputeFreq(String S, List<int[]> freq) { int[] f = new int[26]; for (int i = 0; i < S.length(); ++i) { freq.set(i, f.clone()); freq.get(i)[S.charAt(i) - 'a']++; f = freq.get(i); } } // Function to get the // smallest anagram from L to R public static String smallestAnagram(String S, int L, int R, List<int[]> freq) { String ans = ""; // Finding net frequencies // of character from L to R for (int i = 0; i < 26; i++) { int low = 0; if (L > 0) { low = freq.get(L - 1)[i]; } // Adding characters to string ans for (int j = 0; j < freq.get(R)[i] - low; j++) { ans += (char)('a' + i); } } return ans; } public static void smallestAnagramUtil(String S, int N, List<int[]> queries) { List<int[]> freq = new ArrayList<>(); for (int i = 0; i < N; i++) { freq.add(new int[26]); } preComputeFreq(S, freq); for (int[] x : queries) { int L = x[0]; int R = x[1]; System.out.println(smallestAnagram(S, L, R, freq)); } } // Driver Code public static void main(String[] args) { String S = "bbdfaaacaed"; int N = S.length(); List<int[]> queries = new ArrayList<>(); queries.add(new int[] {0, 4}); queries.add(new int[] {4, 8}); smallestAnagramUtil(S, N, queries); }}//This code is contributed by ik_9 |
Python3
## Python program for the above approach:## Function to calculate the frequencies of all## characters till each index in stringdef preComputeFreq(S, freq): for i in range(len(S)): freq[i] = [0]*26 freq[i][ord(S[i]) - ord('a')]+=1 if(i > 0): for j in range(26): freq[i][j] += freq[i-1][j] ## Function to get the## smallest anagram from L to Rdef smallestAnagram(S, L, R, freq): ans = "" ## Finding net frequencies ## of character from L to R for i in range(26): low = 0; if (L > 0): low = freq[L - 1][i] ## Adding character to string ans for j in range(0, freq[R][i]-low): ans += chr(ord('a') + i) return ansdef smallestAnagramUtil(S, N, queries): freq = [0]*N for i in range(N): freq[i] = [0]*26 preComputeFreq(S, freq) for x in queries: L = x[0] R = x[1] print(smallestAnagram(S, L, R, freq))## Driver codeif __name__=='__main__': S = "bbdfaaacaed" N = len(S) queries = [ [ 0, 4 ], [ 4, 8 ] ] smallestAnagramUtil(S, N, queries) |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to calculate the frequencies of all // characters till each index in string function preComputeFreq(S, freq) { let f = new Array(26).fill(0); for (let i = 0; i < S.length; ++i) { freq[i] = [...f]; freq[i][S[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; f = [...freq[i]]; } return freq; } // Function to get the // smallest anagram from L to R function smallestAnagram(S, L, R, freq) { let ans = ''; // Finding net frequencies // of character from L to R for (let i = 0; i < 26; i++) { let low = 0; if (L > 0) { low = freq[L - 1][i]; } // Adding characters to string ans for (let j = 0; j < freq[R][i] - low; j++) { ans = ans + String.fromCharCode('a'.charCodeAt(0) + i); } } return ans; } function smallestAnagramUtil(S, N, queries) { let freq = new Array(N); for (let i = 0; i < freq.length; i++) { freq[i] = new Array(26).fill(0); } freq = preComputeFreq(S, freq); for (let i = 0; i < queries.length; i++) { let L = queries[i][0]; let R = queries[i][1]; document.write(smallestAnagram(S, L, R, freq) + '<br>'); } } // Driver Code let S = "bbdfaaacaed"; let N = S.length; let queries = [[0, 4], [4, 8]]; smallestAnagramUtil(S, N, queries);// This code is contributed by Potta Lokesh</script> |
C#
using System;using System.Collections.Generic; class GFG { // Function to calculate the frequencies of all // characters till each index in string public static void PreComputeFreq(string S, List<int[]> freq) { int[] f = new int[26]; for (int i = 0; i < S.Length; ++i) { freq[i] = (int[])f.Clone(); freq[i][S[i] - 'a']++; f = freq[i]; } } // Function to get the // smallest anagram from L to R public static string SmallestAnagram(string S, int L, int R, List<int[]> freq) { string ans = ""; // Finding net frequencies // of character from L to R for (int i = 0; i < 26; i++) { int low = 0; if (L > 0) { low = freq[L - 1][i]; } // Adding characters to string ans for (int j = 0; j < freq[R][i] - low; j++) { ans += (char)('a' + i); } } return ans; } public static void SmallestAnagramUtil(string S, int N, List<int[]> queries) { List<int[]> freq = new List<int[]>(); for (int i = 0; i < N; i++) { freq.Add(new int[26]); } PreComputeFreq(S, freq); foreach (int[] x in queries) { int L = x[0]; int R = x[1]; Console.WriteLine(SmallestAnagram(S, L, R, freq)); } } // Driver Code static void Main(string[] args) { string S = "bbdfaaacaed"; int N = S.Length; List<int[]> queries = new List<int[]>() { new int[] {0, 4}, new int[] {4, 8} }; SmallestAnagramUtil(S, N, queries); } } |
Output
abbdf aaaac
Time Complexity: O(Q*N)
Auxiliary Space: O(26*N)
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!
