**Introduction:**

We are given a string of length N and a few queries of the form [L, R]. For each query, we need to find the lexicographically smallest anagram of the substring [L, R].

Let us see a few examples:-

**Input: **

S: bcdaaef

Queries: [[0, 3], [2, 4]]

**Output:**

abcd

aad

**Explanation:**

For the first query, we have “bcda”. The lexicographically smallest anagram of this substring is “abcd”. Similarly, for the second query, we have “daa”. The lexicographically smallest anagram is “aad”

**Input:**

S: badge

Queries: [[1, 4], [0, 3]]

**Output: **

adeg

abdg

**Approach:**

For any String, its lexicographically smallest anagram will be the String in which all the ‘a’ come first, then all the ‘b’ come, then all the ‘c’ come and similarly till ‘z’. We will use the same concept to solve this problem. For each query, we will store the frequency of each character and then generate the answer String by appending all the ‘a’ first and all the ‘b’ and we will do this till ‘z’. We can optimize the part to find the frequency of each character by precomputing them. We will generate a prefix array for each character where freq[i][j] will store the number of (‘a’ + j) characters from the 0th index to the jth index.

We will follow the below steps:-

- We will precompute the freq array where freq[i][j] will store the frequency of the (‘a’+ j) character from the 0th index till the jth index.
- For each query, we will call the precomputeFreq() function to find the smallest anagram of the substring [L, R].
- Now, for each query, we will maintain the
**ans**string and append all the ‘a’ first, then all the ‘b’ till ‘z’/

Refer to the below implementation of the above approach.

#include <bits/stdc++.h> of the substring [L, R]. |

**Time Complexity: O(numberOfQueries * N)**

The time complexity for the above approach used to find the lexicographically smallest anagram is O(numberOfQueries * N)(where N is the length of the String) because for each query in the worst case we need to append all the characters of the input String to the **ans **String.

**Space Complexity: O(26 * N) **

The space complexity for the above code to find the lexicographically smallest anagram is O(26 * N)(where N is the length of the input String) because we are creating a freq array of (26 * N) size to precompute the frequency of each character.