lexicographically smallest anagram

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>
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(26, 0);
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<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;
}
}

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.

FAQs:

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

We first discussed the approach to finding the lexicographically smallest anagram for each query.
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.

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

Introduction:

Approach:

FAQs:

Key Takeaways: