<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) {
        vector<vector<string>> v;
        if(strs.size()==0) return v;
        else if(strs.size()==1){
            v.push_back(strs);
            return v;
        }
        else{
            vector<string> strs01(strs.size());
            for(int i=0; i<strs.size(); i++){
                strs01[i]=strs[i];
                sort(strs01[i].begin(),strs01[i].end());
            }
            // sort(original.begin(),original.end());
            int n = strs01.size();
            quickSort(strs01, strs, 0, n - 1);

            int count = 0;
            for(int i=1,j=0; i<strs.size(); i++){
                if(strs01[i]==strs01[i-1] && i==strs.size()-1){
                    count++;
                    vector<string> s;
                    for(int k=j; k<=count; k++){
                        s.push_back(strs[k]);
                    }
                    v.push_back(s);
                    break;
                }
                else if(strs01[i]==strs01[i-1]){
                    count++;
                }
                else{
                    vector<string> s;
                    for(int k=j; k<=count; k++){
                        s.push_back(strs[k]);
                    }
                    count++;
                    j=count;
                    v.push_back(s);
                }
                if(i==strs.size()-1){
                    vector<string> s;
                    s.push_back(strs[i]);
                    v.push_back(s);

                }

            }
        return v;
        }
    }
    int partition(vector<string> &vec,vector<string> &strs, int low, int high){
        // Selecting last element as the pivot
        string pivot = vec[high];
        // Index of elemment just before the last element
        // It is used for swapping
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++) {
            // If current element is smaller than or
            // equal to pivot
            if (vec[j] <= pivot) {
                i++;
                swap(vec[i], vec[j]);
                swap(strs[i], strs[j]);
            }
        }
        // Put pivot to its position
        swap(vec[i + 1], vec[high]);
        swap(strs[i + 1], strs[high]);
    
        // Return the point of partition
        return (i + 1);
    }

    void quickSort(vector<string> &vec,vector<string> &strs, int low, int high) {
    
        // Base case: This part will be executed till the starting
        // index low is lesser than the ending index high
        if (low < high) {
    
            // pi is Partitioning Index, arr[p] is now at
            // right place
            int pi = partition(vec, strs, low, high);
    
            // Separately sort elements before and after the
            // Partition Index pi
            quickSort(vec, strs, low, pi - 1);
            quickSort(vec, strs, pi + 1, high);
        }
    }
};
21240