Xenny and Partially Sorted Strings

Xenny had a list of N strings of equal length. He wanted to sort them by the first M characters only. That means, while sorting the list of strings, he only wanted to consider the first M characters of each string.

Help Xenny to find out the Kth string in the list after he sorts them.

Note: Xenny wanted to perform stable sorting.
Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

Example:

Input:  n = 3, k = 1, m = 3, s = {"abcdef","abcaaa","aabaaa"}
Output: aabaaa

Approach

C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<string, int> pi;

string partialSortedString(int n, int k,
                           int m, vector<string> &s)
{
    priority_queue<pi, vector<pi>, greater<pi>> q;
    for (int i = 0; i < n; i++)
    {
        if (s[i].size() == m)
            q.push({s[i], i + 1});
        else if (s[i].size() != m)
        {
            string str = "";
            string p = s[i];
            for (int j = 0; j < m; j++)
                str += p[j];
            q.push({str, i + 1});
        }
    }
    int cnt = 0, j = 0;
    while (!q.empty())
    {
        pair<string, int> p1 = q.top();
        q.pop();
        cnt++;
        if (cnt == k)
        {
            j = p1.second;
            break;
        }
    }
    return s[j - 1];
}
int main()
{

    int n = 3, k = 1, m = 3;

    vector<string> s = {"abcdef",
                        "abcaaa",
                        "aabaaa"};

    cout << partialSortedString(n, k, m, s) << "\n";

    return 0;
}