X-th Smallest Substring Lexicographically in C++

In this problem, we are given a string str and Q queries. Each Query has a number X. Our task is to create a program to solve the Queries to answer the X-th smallest sub-string lexicographically in C++.

Problem Description

We need to find the Xth lexicographically smallest substring for each query i.e. based on alphabetical order sorting we will have to find Xth substring.

Let’s take an example to understand the problem,

Input: str = “point”

Q = 4 query = {4, 7, 2, 13}

Output:n, oi, in, poin

Explanation

All substrings of str in lexicographical order are−

i, in, int, n, nt, o, oi, oin, oint, p, po, poi, poin, point, t

4th sub-string - n

7th sub-string - oi

2nd sub-string - in

13th sub-string - poin

Solution Approach

A simple solution will be generating all possible substrings of the string,storing them in a data structure, and then sorting them in lexicographical order i.e. alphabetical order. Then for the X in the queries, we need to print the corresponding subarray from the structure.

To store the substrings, we will use vectors.

Example

Live Demo

#include <bits/stdc++.h>
using namespace std;
vector<string> substrings;
void find_SortSubstrings(string s) {
   int len = s.size();
   for (int i = 0; i < len; i++) {
      string dup = "";
      for (int j = i; j < len; j++) {
         dup += s[j];
         substrings.push_back(dup);
      }
   }
   sort(substrings.begin(), substrings.end());
}
int main(){
   string str = "point";
   find_SortSubstrings(str);
   int Q = 4;
   int query[] = { 4, 9, 5, 15 };
   for (int i = 0; i < Q; i++)
      cout<<"Query "<<(i+1)<<" : The "<<query[i]<<"th smallest sub-string lexicographically is "<<substrings[query[i] - 1] << endl;
      return 0;
}

Output

Query 1 : The 4th smallest sub-string lexicographically is n
Query 2 : The 9th smallest sub-string lexicographically is oint
Query 3 : The 5th smallest sub-string lexicographically is nt
Query 4 : The 15th smallest sub-string lexicographically is t