Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction:
2.
Approach:
3.
FAQs:
4.
Key Takeaways: 
Last Updated: Mar 27, 2024

Lexicographically smallest anagram of given string in range [L, R] for Q queries

Author Nishant Rana
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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:-

  1. 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.
  2. For each query, we will call the precomputeFreq() function to find the smallest anagram of the substring [L, R].
  3. 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>
using namespace std;
 
/*
  This function will preCompute
  the frequencies of each character
  till the ith index.
*/
void preComputeFreq(string& S, vector<vector<int> >& freq)
{
    vector<int> f(260);
    for (int i = 0; i < S.size(); ++i) {
        freq[i] = f;
        freq[i][S[i] - 'a']++;
 
        f = freq[i];
    }
}
 
/*
  This function will return the
  lexicographically smallest anagram 

   of the substring [L, R].
*/
string smallestAnagram(string& S, int L, int R, vector<vector<int> >& freq)
{
    string ans;
 
    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<intint> >& queries)
{
    vector<vector<int> > freq(N, vector<int>(260));
    preComputeFreq(S, freq);
 
    for (auto x : queries) {
        int L = x.first;
        int R = x.second;
        cout << smallestAnagram(S, L, R, freq)
          << endl;
    }
}

 

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.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs:

  1. What is freq[i][j] storing?
    • The freq[i][j] is storing the frequency of the (‘a’+j)th character from the 0th index to the jth index.
  2. What is the time complexity for the optimized approach?
    • The time complexity of the approach to find the lexicographical smallest  substring 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

 

Key Takeaways: 

In this blog, we have covered the following things:

  1. We first discussed the approach to finding the lexicographically smallest anagram for each query.
  2. Then we saw how to implement the approach discussed to find the lexicographically smallest anagram for each query.


Check out this problem - Multiply Strings

If you want to learn more about Strings and practice some questions requiring you to take your basic knowledge on Strings a notch higher, then you can visit our Guided Path for String

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Maximize the sum of the product of two arrays at corresponding indexes by reversing at most one subarray of the first array
Next article
Minimum Characters Require to Remove from Binary String to Sort it in Ascending Order
Live masterclass