<p>Given an array of strings <code>strs</code>, group the <span data-keyword="anagram">anagrams</span> together. You can return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;eat&quot;,&quot;tea&quot;,&quot;tan&quot;,&quot;ate&quot;,&quot;nat&quot;,&quot;bat&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;bat&quot;],[&quot;nat&quot;,&quot;tan&quot;],[&quot;ate&quot;,&quot;eat&quot;,&quot;tea&quot;]]</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>There is no string in strs that can be rearranged to form <code>&quot;bat&quot;</code>.</li>
	<li>The strings <code>&quot;nat&quot;</code> and <code>&quot;tan&quot;</code> are anagrams as they can be rearranged to form each other.</li>
	<li>The strings <code>&quot;ate&quot;</code>, <code>&quot;eat&quot;</code>, and <code>&quot;tea&quot;</code> are anagrams as they can be rearranged to form each other.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;&quot;]]</span></p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;a&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;a&quot;]]</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= strs.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= strs[i].length &lt;= 100</code></li>
	<li><code>strs[i]</code> consists of lowercase English letters.</li>
</ul>


// class Solution {
// public:
//     vector<vector<string>> groupAnagrams(vector<string>& strs) {
//         unordered_map<string, vector<string>> ans;

//         for (string& s : strs) {
//             string key = s;
//             sort(key.begin(), key.end());
//             ans[key].push_back(s);
//         }

//         vector<vector<string>> result;
//         for (auto& entry : ans) {
//             result.push_back(entry.second);
//         }

//         return result;        
//     }
// }; 

// class Solution {
// public:
//     vector<vector<string>> groupAnagrams(vector<string>& strs){

//     }
// };


class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        vector<string> sortedStrs(n);
        // Create a vector of sorted strings
        for (int i = 0; i < n; ++i) {
            sortedStrs[i] = strs[i];
            sort(sortedStrs[i].begin(), sortedStrs[i].end());
        }
        // Sort the original strings based on their sorted versions
        vector<int> indices(n);
        for (int i = 0; i < n; ++i) {
            indices[i] = i;
        }
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            return sortedStrs[a] < sortedStrs[b];
        });
        // Group the anagrams based on the sorted strings
        vector<vector<string>> result;
        vector<string> currentGroup;
        currentGroup.push_back(strs[indices[0]]);
        for (int i = 1; i < n; ++i) {
            if (sortedStrs[indices[i]] == sortedStrs[indices[i - 1]]) {
                currentGroup.push_back(strs[indices[i]]);
            } else {
                result.push_back(currentGroup);
                currentGroup.clear();
                currentGroup.push_back(strs[indices[i]]);
            }
        }
        result.push_back(currentGroup);
        
        return result;
    }
};
17259