hash-maps/group_titles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "75aa47ce-4ab4-4022-b899-ce06858bf267",
   "metadata": {},
   "source": [
    "**Problem Statement**\n",
    "\n",
    "Implement a feature that takes in a list of strings and groups them based on similarity. \n",
    "\n",
    "Two strings are considered similar if they are anagrams of each other. An anagram is a word or phrase formed by rearranging the letters of another, using all the original letters exactly once.\n",
    "\n",
    "Example: \n",
    "\n",
    "Input: `[\"listen\", \"silent\", \"enlist\", \"google\", \"gogole\", \"cat\", \"act\"]` \n",
    "\n",
    "Output: `[[\"listen\", \"silent\", \"enlist\"], [\"google\", \"gogole\"], [\"cat\", \"act\"]]`\n",
    "\n",
    "The goal is to create a function that can efficiently group these strings into sets of anagrams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "cb6db857-9be1-49f2-a959-6a860501778c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution\n",
    "from typing import List, Dict\n",
    "def group_titles(titles: List[str]) -> List[List[str]]:\n",
    "    results = {}\n",
    "    for word in titles:\n",
    "        count = [0] * 26\n",
    "        for c in word:\n",
    "            index = ord(c) - ord(\"a\")\n",
    "            count[index] += 1\n",
    "        key = tuple(count)\n",
    "        if key in results:\n",
    "            results[key].append(word)\n",
    "        else:\n",
    "            results[key] = [word]\n",
    "    return list(results.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "87310802-683c-46f3-9313-069c09078314",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['listen', 'silent', 'enlist'], ['google', 'gogole'], ['cat', 'act']]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "titles = [\"listen\", \"silent\", \"enlist\", \"google\", \"gogole\", \"cat\", \"act\"]\n",
    "group_titles(titles)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebd5462f-5b60-4b61-bc93-d8febeb60fbd",
   "metadata": {},
   "source": [
    "The time complexity of the solution is $O(N \\cdot K)$, where N is the number of words and K is the maximum length of the word. This is because you iterate through each word and then through each character in the word to create the count key."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ec468fc-c99c-457c-b905-20575ac546d7",
   "metadata": {},
   "source": [
    "Since every string is being stored as a value in the dictionary whose size can be N, and the size of the string is K, so the space complexity is $O(N \\cdot K)$,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "009eef51-f21c-4466-86a1-9f70aa465023",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}