Skip to content

Equivalent Transformation

Table of Contents

3375. Minimum Operations to Make Array Values Equal to K

2914. Minimum Number of Changes to Make Binary String Beautiful

3365. Rearrange K Substrings to Form Target String

1657. Determine if Two Strings Are Close

2551. Put Marbles in Bags

1585. Check If String Is Transformable With Substring Sort Operations

1040. Moving Stones Until Consecutive II

249. Group Shifted Strings 👑

49. Group Anagrams

from collections import defaultdict
from typing import List


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """Counting Hash Map: O(n * k) time, O(n) space.
        Words with the same 26-letter frequency tuple are anagrams.
        """
        groups = defaultdict(list)

        for word in strs:
            counts = [0] * 26
            for ch in word:
                counts[ord(ch) - ord("a")] += 1
            groups[tuple(counts)].append(word)

        return list(groups.values())


def test_group_anagrams():
    def normalized(groups):
        return sorted(sorted(group) for group in groups)

    s = Solution()
    result = s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    assert normalized(result) == [
        ["ate", "eat", "tea"],
        ["bat"],
        ["nat", "tan"],
    ]
    assert normalized(s.groupAnagrams([""])) == [[""]]
    assert normalized(s.groupAnagrams(["a"])) == [["a"]]

#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

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

        for (string& s : strs) {
            string sorted = s;
            ranges::sort(sorted);
            map[sorted].push_back(s);
        }

        vector<vector<string>> res;

        for (auto& kv : map) {
            res.push_back(kv.second);
        }
        return res;
    }
};

int main() {
    Solution solution;
    vector<string> strs = {"eat", "tea", "tan"};
    vector<vector<string>> res = solution.groupAnagrams(strs);
    assert((res == vector<vector<string>>{{"eat", "tea"}, {"tan"}} ||
            res == vector<vector<string>>{{"tan"}, {"eat", "tea"}}));

    return 0;
}

1183. Maximum Number of Ones 👑