Two distinct character substring.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Find longest substring consisting of two distinct characters\n",
    "Given a string, return its longest substring that is composed by at most two distinct characters, e.g. \"01201340101234123\" -> \"0101\", \"abbaccdaababaaacaaacbaabcdads\" -> \"aababaaa\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "Two pointer approach: Let current substring be defined by left and right pointers counts of its composing characters stored in a dictionary. Right pointer keeps incrementing as long as the size of dictionary (number of distinct characters in current substring) is less than 3. When it reaches 3, left pointer increments until the count is back to 2. On every increment of right pointer we check against global maximum and two pointers associated with it. They are updated when current subtring is longer than any substring we've seen so far."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def longest_with_two(s):\n",
    "    if not s:\n",
    "        return s\n",
    "    left = right = max_left = max_right = 0\n",
    "    max_len = 1\n",
    "    counts = {s[0]: 1}\n",
    "    while right < len(s)-1:\n",
    "        if len(counts) < 3:\n",
    "            if right-left > max_len:\n",
    "                max_len = right-left\n",
    "                max_left = left\n",
    "                max_right = right\n",
    "            right += 1\n",
    "            if s[right] in counts:\n",
    "                counts[s[right]] += 1\n",
    "            else:\n",
    "                counts[s[right]] = 1\n",
    "        else:\n",
    "            while len(counts) > 2:\n",
    "                if counts[s[left]] == 1:\n",
    "                    del counts[s[left]]\n",
    "                else:\n",
    "                    counts[s[left]] -= 1\n",
    "                left += 1\n",
    "                \n",
    "    return s[max_left:max_right+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'aababaaa'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_with_two(\"abbaccdaababaaacaaacbaabcdads\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [python3]",
   "language": "python",
   "name": "Python [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.4.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}