practice-geeksforgeeks-strings.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Print Anagrams Together\n",
    "Given an array of strings, return all groups of strings that are anagrams. The groups must be created in order of their appearance in the original array. Look at the sample case for clarification.\n",
    "\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "N = 5\n",
    "words[] = {act,god,cat,dog,tac}\n",
    "Output: \n",
    "god dog\n",
    "act cat tac\n",
    "Explanation:\n",
    "There are 2 groups of\n",
    "anagrams \"god\", \"dog\" make group 1.\n",
    "\"act\", \"cat\", \"tac\" make group 2.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "N = 3\n",
    "words[] = {no,on,is}\n",
    "Output: \n",
    "no on\n",
    "is\n",
    "Explanation:\n",
    "There are 2 groups of\n",
    "anagrams \"no\", \"on\" make group 1.\n",
    "\"is\" makes group 2. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['act', 'cat', 'tac'], ['god', 'dog']]\n",
      "[['no', 'on'], ['is']]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def Anagrams(self,words,n):\n",
    "        res={}\n",
    "        def createKey(index):\n",
    "            return ''.join(list(sorted(words[i])))\n",
    "\n",
    "        for i in range(n):\n",
    "            res[words[i]] = createKey(i)\n",
    "        resLen = len(res)\n",
    "        final=[[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if res[words[j]] == res[words[i]]:\n",
    "                    final[i].append(words[j])\n",
    "        result =[]\n",
    "        for i in final:\n",
    "            if i not in result:\n",
    "                result.append(i)\n",
    "        return result\n",
    "sol= Solution()\n",
    "# print(findAnagram('act','tacs'))\n",
    "print(sol.Anagrams(['act','god','cat','dog','tac'],5))\n",
    "print(sol.Anagrams(['no','on','is'],3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Longest Even Length Substring \n",
    "\n",
    "For given string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits.\n",
    " \n",
    "\n",
    "Input:\n",
    "\n",
    "The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.\n",
    "Each test case contains a string string of length N.\n",
    "\n",
    "Output:\n",
    "\n",
    "Print length of the longest substring of length 2k such that sum of left k elements is equal to right k elements and if there is no such substring print 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def func(self,arr,n):\n",
    "        pass\n",
    "\n",
    "sol = Solution()        \n",
    "print(sol.func([],0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Shortest Common Supersequence\n",
    "\n",
    "\n",
    "Given two strings X and Y of lengths m and n respectively, find the length of the smallest string which has both, X and Y as its sub-sequences.\n",
    "Note: X and Y can have both uppercase and lowercase letters.\n",
    "\n",
    "Example 1\n",
    "\n",
    "Input:\n",
    "X = abcd, Y = xycd\n",
    "Output: 6\n",
    "Explanation: Shortest Common Supersequence\n",
    "would be abxycd which is of length 6 and\n",
    "has both the strings as its subsequences.\n",
    "\n",
    "Example 2\n",
    "\n",
    "Input:\n",
    "X = efgh, Y = jghi\n",
    "Output: 6\n",
    "Explanation: Shortest Common Supersequence\n",
    "would be ejfghi which is of length 6 and\n",
    "has both the strings as its subsequences."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "6\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "#User function Template for python3\n",
    "class Solution:\n",
    "    #Function to find length of shortest common supersequence of two strings.\n",
    "    def shortestCommonSupersequence(self, str1, str2, m, n):\n",
    "        dic={}\n",
    "        for i in str1:\n",
    "            if i not in dic:\n",
    "                dic[i]=i\n",
    "        for i in str2:\n",
    "            if i not in dic:\n",
    "                dic[i]=i\n",
    "#         print(dic)\n",
    "        return len(dic)\n",
    "         #code here\n",
    "sol = Solution()\n",
    "print(sol.shortestCommonSupersequence('abcd','xycd',4,4)) # 6\n",
    "print(sol.shortestCommonSupersequence('efgh','jghi',4,4)) # 6\n",
    "print(sol.shortestCommonSupersequence('hxmngqmf','gnapcnty',8,8)) # 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}