02-Strings.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.0 Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 Find anagram indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Given a word $w$ and string $s$ find the starting indices of all of the anagrams of $s$ in $w$.\n",
    "\n",
    "anagram (def.)\n",
    "> An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.  For example, `adobe` can be rearranged into `abode`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_anagram_indices (__main__.AnagramIndicesTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.004s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7fea30ac1e80>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "import unittest\n",
    "\n",
    "\n",
    "def anagram_indices(word, s):\n",
    "    \"\"\"Find the starting indices of anagrams of s in word.\"\"\"\n",
    "\n",
    "    # Incrementally update a character count frequency map as\n",
    "    # you move a sliding window of length s over word.\n",
    "    # The count in the map associated with each character\n",
    "    # has the following invariants:\n",
    "    # 0  = character appears with same frequency in window\n",
    "    # <0 = character not in s appears in window\n",
    "    # >0 = character in s appears with overabundance in window\n",
    "    wfreq, inds = collections.defaultdict(int), []\n",
    "\n",
    "    # Initialize the frequency with contents of s.\n",
    "    for char in s:\n",
    "        wfreq[char] += 1\n",
    "        \n",
    "    # Decrement the frequency with the characters in first window.\n",
    "    # Instead of explicitly keeping 0-valued entries in the map,\n",
    "    # delete such entries so that the test for anagrams is changed\n",
    "    # to be a test where map is empty when window contains anagram.\n",
    "    for char in word[:len(s)]:\n",
    "        wfreq[char] -= 1  # Decrement means character in window.\n",
    "        if wfreq[char] == 0:\n",
    "            del wfreq[char]\n",
    "    if len(wfreq) == 0:\n",
    "        inds.append(0)\n",
    "\n",
    "    # Iterate from [len(s), len(word)] incrementally updating map.\n",
    "    for ind in range(len(s), len(word)):\n",
    "        cleft, cright = word[ind-len(s)], word[ind]\n",
    "        wfreq[cleft] += 1  # Increment means character not in window.\n",
    "        if wfreq[cleft] == 0:\n",
    "            del wfreq[cleft]\n",
    "        wfreq[cright] -= 1  # Decrement means character in window.\n",
    "        if wfreq[cright] == 0:\n",
    "            del wfreq[cright]\n",
    "        if len(wfreq) == 0:\n",
    "            inds.append(ind-len(s)+1)\n",
    "\n",
    "    return inds\n",
    "\n",
    "\n",
    "class AnagramIndicesTest(unittest.TestCase):\n",
    "\n",
    "    def test_anagram_indices(self):\n",
    "        case = collections.namedtuple('case', ['word','s','expected'])\n",
    "        cases = [\n",
    "            case('abxaba', 'ab', [0,3,4]),\n",
    "            # Corner case with repeating elements of s.\n",
    "            case('abxabb', 'ab', [0,3]),\n",
    "            # Corner case with repeating elements followed by anagram.\n",
    "            case('abxabba', 'ab', [0,3,5]),\n",
    "            # Corner case with back-to-back-to-back.\n",
    "            case('liveevilvile', 'live', [0,4,8]),\n",
    "            # Corner case with same characters but different frequency.\n",
    "            case('ttwwt', 'wwt', [1,2]),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            rcv = anagram_indices(c.word ,c.s)\n",
    "            self.assertEqual(rcv, c.expected)\n",
    "\n",
    "\n",
    "unittest.main(AnagramIndicesTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 Generate palindrome pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Given a list of words, return all possible palindromes formed by concatenating pairs of words from the list.\n",
    "\n",
    "palindrome (def.)\n",
    "> A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward.  For example, the word `madam` is a palindrome."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_palindrome_pairs (__main__.PalindromePairsTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.003s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7fea30a4bcc0>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "import unittest\n",
    "\n",
    "\n",
    "def is_palindrome(word):\n",
    "    \"\"\"Return True when a word is a palindrome.\"\"\"\n",
    "    if len(word) < 2:\n",
    "        return True  # Empty and 1-character strings are palindromes.\n",
    "    return word == ''.join(reversed(word))\n",
    "\n",
    "\n",
    "def palindrome_pairs(words):\n",
    "    \"\"\"Return palindrome pairs formed by concatenating pairs of words.\"\"\"\n",
    "    pairs, lookup = [], set(words)\n",
    "\n",
    "    for word in words:\n",
    "        # Check whether the palindrome of the word is in the input list.\n",
    "        if not is_palindrome(word):\n",
    "            reversed_word = ''.join(reversed(word))\n",
    "            if reversed_word in lookup:\n",
    "                pairs.append((word, reversed_word))\n",
    "\n",
    "        # Check whether word prefix forms palindrome.\n",
    "        for ind in range(0,len(word)-1):\n",
    "            if not(is_palindrome(word[ind+1:])):  # Suffix not palindrome.\n",
    "                continue\n",
    "            reversed_word = ''.join(reversed(word[:ind+1]))\n",
    "            if reversed_word in lookup:\n",
    "                pairs.append((word, reversed_word))\n",
    "        \n",
    "        # Check whether word suffix forms palindrome.\n",
    "        for ind in range(len(word)-1,0,-1):\n",
    "            if not(is_palindrome(word[:ind])):  # Prefix not palindrome.\n",
    "                continue\n",
    "            reversed_word = ''.join(reversed(word[ind:]))\n",
    "            if reversed_word in lookup:\n",
    "                pairs.append((reversed_word, word))\n",
    "\n",
    "    return pairs\n",
    "\n",
    "\n",
    "class PalindromePairsTest(unittest.TestCase):\n",
    "\n",
    "    def test_palindrome_pairs(self):\n",
    "        case = collections.namedtuple('case', ['input','expected'])                                                                   \n",
    "        cases = [\n",
    "            # Palindrome formed without overlapping prefix or suffix.\n",
    "            case(['foo','oof'], [('foo','oof'),('oof','foo')]),\n",
    "            # One palindrome pair found by matching prefix to `dc`.\n",
    "            case(['cdaba','dc'], [('cdaba', 'dc')]),\n",
    "            case(['cdabc','dc'], []),  # Suffix is not palindrome.\n",
    "            # One palindrome pair found by matching suffix to `dc`.\n",
    "            case(['abacd','dc'], [('dc','abacd')]),\n",
    "            case(['abccd','dc'], []),  # Prefix is not palindrome.\n",
    "            # Words are palindromes, but no pair form palindromes.\n",
    "            case(['aba', 'cbc'], []),\n",
    "            # Fully general case mixing palindromes and non-palindromes.\n",
    "            case([\"ma\",\"dam\",\"nurses\",\"run\",\"foo\",\"oof\",\"fo\",\"f\"],\n",
    "                 [('ma','dam'),\n",
    "                  ('nurses','run'),\n",
    "                  ('foo','f'),('foo','oof'),\n",
    "                  ('oof','foo'),\n",
    "                  ('fo','f'),('fo','oof'),\n",
    "                  ('f','oof')]),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            rcv = palindrome_pairs(c.input)\n",
    "            self.assertEqual(sorted(rcv), sorted(c.expected))\n",
    "\n",
    "\n",
    "unittest.main(PalindromePairsTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3 Print a string in zigzag form"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Implement a function that takes a string, named s, and a height, named h, and prints the string in zigzag form.\n",
    "\n",
    "#### Examples\n",
    "input\n",
    "```\n",
    "helloworldzigzag\n",
    "1234567890123456\n",
    "```\n",
    "\n",
    "h=2\n",
    "```\n",
    "h l o o l z g a\n",
    " e l w r d i z g\n",
    "```\n",
    "\n",
    "h=4\n",
    "```\n",
    "h     o     g\n",
    " e   w r   i z\n",
    "  l o   l z   a\n",
    "   l     d     g\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_zigzag (__main__.ZigzagTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.004s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7fea30a316d8>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "import io\n",
    "import unittest\n",
    "\n",
    "\n",
    "def zigzag(string, height):\n",
    "    \"\"\"Return a printed string of given height in zigzag form.\"\"\"\n",
    "    strbuff = io.StringIO()\n",
    "    # Print the string line-by-line into the buffer varying the\n",
    "    # stride between characters depending upon whether we are \n",
    "    # printing characters from top-to-bottom or bottom-to-top.\n",
    "    for h in range(1,height+1):\n",
    "        # stride1 refers to top-to-bottom and stride2 bottom-to-top.\n",
    "        stride1, stride2 = (height*2) - (2*h), 2*h-2\n",
    "        # Alternating stride isn't necessary for top and bottom.\n",
    "        stride2 = stride1 if h == 1 else stride2\n",
    "        stride1 = stride2 if h == height else stride1\n",
    "        strbuff.write(' '*(h-1))  # Add leading padding.\n",
    "        # Print each character separated by the stride length.\n",
    "        ind, stride = h-1, stride1\n",
    "        while True:\n",
    "            strbuff.write(string[ind])  # Print character.\n",
    "            ind += stride\n",
    "            if not(ind < len(string)):\n",
    "                break\n",
    "            strbuff.write(' '*(stride-1))  # Space between characters.\n",
    "            stride = stride2 if stride == stride1 else stride1  # Toggle.\n",
    "        strbuff.write('\\n')\n",
    "    return strbuff.getvalue()\n",
    "\n",
    "\n",
    "class ZigzagTest(unittest.TestCase):\n",
    "\n",
    "    helloworld = 'helloworldzigzag'\n",
    "    \n",
    "    helloworld_h2 = \\\n",
    "\"\"\"\n",
    "h l o o l z g a\n",
    " e l w r d i z g\n",
    "\"\"\"\n",
    "\n",
    "    helloworld_h4 = \\\n",
    "\"\"\"\n",
    "h     o     g\n",
    " e   w r   i z\n",
    "  l o   l z   a\n",
    "   l     d     g\n",
    "\"\"\"\n",
    "\n",
    "    helloworld_h5 = \\\n",
    "\"\"\"\n",
    "h       l\n",
    " e     r d     g\n",
    "  l   o   z   a\n",
    "   l w     i z\n",
    "    o       g\n",
    "\"\"\"\n",
    "\n",
    "    def test_zigzag(self):\n",
    "        case = collections.namedtuple('case', ['s','h','expected'])\n",
    "        cases = [\n",
    "            case(self.helloworld, 2, self.helloworld_h2),\n",
    "            case(self.helloworld, 4, self.helloworld_h4),\n",
    "            case(self.helloworld, 5, self.helloworld_h5),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            rcv = zigzag(c.s, c.h)\n",
    "            # NOTE(marcoemorais): Remove leading linebreak from t.q.s.\n",
    "            expected = c.expected[1:]\n",
    "            self.assertEqual(rcv, expected)\n",
    "\n",
    "\n",
    "unittest.main(ZigzagTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.4 Determine smallest rotated string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Given a string and length $k$, determine the lexicographically smallest string that can be created by rotating $k$ characters from the beginning of the string to the end.\n",
    "\n",
    "lexicographic order (def.)\n",
    "> Generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters.  For example, the lexicographic of the string `ab` comes before `ac`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}