Ordenar la array de strings en función del rango de substring dado

Dados dos enteros positivos I y X y una array de strings arr[] , la tarea es ordenar la array de strings dada en función de las substrings a partir del índice I de tamaño X .

Ejemplos: 

Entrada: I = 2, X = 2, arr[] = { “baqwer”, “zacaeaz”, “aaqzzaa”, “aacaap”, “abbatyo”, “bbbacztr”, “bbbdaaa” } 
Salida: abbatyo bbbacztr bbbdaaa aacaap zacaeaz baqwer aaqzzaa 
Explicación: 
Todas las substrings a partir del índice I = 2 y de tamaño x = 2 son {“qw”, “ca”, “qz”, “ca”, “ba”, “ba”, “bd”} . 
Ordenarlos en orden creciente lexicográfico da {“ba”, “ba”, “bd”, “ca”, “ca”, “qw”, “qz” }, luego imprime la string original correspondiente en este orden.

Entrada: I = 1, X = 3, arr[] = { «enviar», «fuente», «habilidades», «epidemia», «amplia», «manzana»} 
Salida: enviar habilidades epidémicas amplia fuente de manzana  

Enfoque: la idea es crear una substring de todas las strings en la array dada a partir del índice I de tamaño X y mantener el recuento de pares de una substring con la string correspondiente en un mapa de pares. Después de insertar en el mapa de pares. Después de insertar, recorra el mapa e imprima la string.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the given array
// of strings based on substring
void sortArray(vector<string> s,
               int l, int x)
{
    // Map of pairs to sort vector
    // of strings
    map<pair<string, string>, int> mp;
 
    for (int i = 0; i < s.size(); i++) {
 
        // Create substring from index
        // 'l' and of size 'X'
        string part = s[i].substr(l, x);
 
        // Insert in Map
        mp[{ part, s[i] }] += 1;
    }
 
    // Print the sorted vector of strings
    for (auto it = mp.begin();
         it != mp.end(); ++it) {
 
        // Traverse the number of time
        // a string is present
        for (int j = 0; j < it->second; j++) {
 
            // Print the string
            cout << it->first.second << ' ';
        }
    }
}
 
// Driver Code
int main()
{
    // Given array of strings
    vector<string> arr;
    arr = { "baqwer", "zacaeaz", "aaqzzaa",
            "aacaap", "abbatyo", "bbbacztr",
            "bbbdaaa" };
 
    // Given I and X
    int I = 2, X = 2;
 
    // Function Call
    sortArray(arr, I, X);
    return 0;
}

abbatyo bbbacztr bbbdaaa aacaap zacaeaz baqwer aaqzzaa

Complejidad de tiempo: O(N*log N) 
Espacio auxiliar: O(N)