    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Algorithm: List\n",
      "\n",
      "Since Python strings are immutable, we'll use a list of characters to build the compressed string representation.  We'll then convert the list to a string.\n",
      "\n",
      "* Calculate the size of the compressed string\n",
      "    * Note the constraint about compressing only if it saves space\n",
 
</s> remove   {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm: Byte Array\n",
    "\n",
    "As a bonus solution, we can also solve this problem with a byte array.\n",
    "\n",
    "The byte array algorithm similar when using a list, except we will need to work with the bytearray's character codes (using the function ord) instead of the characters as when we implemented this solution with a list.\n",
    "\n",
    "Complexity:\n",
    "* Time: O(n)\n",
    "* Space: O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code: Byte Array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def compress_string_alt(string):\n",
    "    if string is None or len(string) == 0:\n",
    "        return string\n",
    "    \n",
    "    # Calculate the size of the compressed string\n",
    "    size = 0\n",
    "    last_char_code = string[0]\n",
    "    for char_code in string:\n",
    "        if char_code != last_char_code:\n",
    "            size += 2\n",
    "            last_char_code = char_code\n",
    "    size += 2\n",
    "    \n",
    "    # If the compressed string size is greater than \n",
    "    # or equal to string size, return string    \n",
    "    if size >= len(string):\n",
    "        return string\n",
    "    \n",
    "    # Create compressed_string\n",
    "    compressed_string = bytearray(size)\n",
    "    pos = 0\n",
    "    count = 0\n",
    "    last_char_code = string[0]\n",
    "    for char_code in string:\n",
    "        if char_code == last_char_code:\n",
    "            count += 1\n",
    "        else:\n",
    "            compressed_string[pos] = last_char_code\n",
    "            compressed_string[pos+1] = ord(str(count))\n",
    "            pos += 2\n",
    "            count = 1\n",
    "            last_char_code = char_code\n",
    "    compressed_string[pos] = last_char_code\n",
    "    compressed_string[pos+1] = ord(str(count))\n",
    "    return str(compressed_string)"
   ]
  },
 </s> add  </s> remove     "* [Algorithm: List](#Algorithm:-List)\n",
    "* [Code: List](#Code:-List)\n",
    "* [Algorithm: Byte Array](#Algorithm:-Byte-Array)\n",
    "* [Code: Byte array](#Code:-Byte-Array)\n",
 </s> add     "* [Algorithm](#Algorithm)\n",
    "* [Code](#Code)\n", </s> remove     "## Code: List"
 </s> add     "## Code" </s> remove     try:
        test.test_compress(compress_string_alt)
    except NameError:
        # Alternate solutions are only defined
        # in the solutions file
        pass
 </s> add  </s> remove    "execution_count": 4,
 </s> add    "execution_count": 3,
    "## Algorithm\n",
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
    "## Algorithm\n",
      "\n",
      "Since Python strings are immutable, we'll use a list of characters to build the compressed string representation.  We'll then convert the list to a string.\n",
      "\n",
      "* Calculate the size of the compressed string\n",
      "    * Note the constraint about compressing only if it saves space\n",
keep keep keep keep replace keep keep keep keep keep
 Removed bytearray solution, needs some tweaks to make it work with Python 3. 
arrays_strings/compress/compress_solution.ipynb