original_string values in sorted order.

Complexity

⏰ Time complexity: O(N * K log K + N log N * K) – sorting characters inside each string costs O(K log K) per string; the sort of N keys costs O(N log N) comparisons and each comparison of keys takes up to O(K).
🧺 Space complexity: O(N * K) – storing the key for each string (pair array) requires extra space proportional to total input.

Code

[{"language":"C++","code":"#include <algorithm>\n#include <string>\n#include <vector>\n\nusing std::pair;\nusing std::string;\nusing std::vector;\n\nclass Solution {\npublic:\n  void sortAnagrams(vector<string>& arr) {\n    vector<pair<string, string>> pairs;\n    pairs.reserve(arr.size());\n    for (auto &s : arr) {\n      string key = s;\n      std::sort(key.begin(), key.end());\n      pairs.emplace_back(key, s);\n    }\n    std::sort(pairs.begin(), pairs.end(), [](const pair<string,string>& a, const pair<string,string>& b){\n      return a.first < b.first;\n    });\n    for (size_t i = 0; i < pairs.size(); ++i)\n      arr[i] = pairs[i].second;\n  }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;algorithm></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;string></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;vector></span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">using</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> std</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">::pair;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">using</span><span style=\"color:#6F42C1;--shiki-dark:#B392F

Related Tags

Continue Practicing