HR_Unique_Letter_String.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "8\n",
      "30\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "A character is unique in string S if it occurs exactly once in it.\n",
    "\n",
    "For example, in string S = \"LETTER\", the only unique characters are \"L\" and \"R\".\n",
    "\n",
    "Let's define UNIQ(S) as the number of unique characters in string S.\n",
    "\n",
    "For example, UNIQ(\"LETTER\") =  2.\n",
    "\n",
    "Given a string S, calculate the sum of UNIQ(substring) over all non-empty substrings of S.\n",
    "\n",
    "If there are two or more equal substrings at different positions in S, we consider them different.\n",
    "\n",
    "Since the answer can be very large, retrun the answer modulo 10 ^ 9 + 7.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: \"ABC\"\n",
    "Output: 10\n",
    "Explanation: All possible substrings are: \"A\",\"B\",\"C\",\"AB\",\"BC\" and \"ABC\".\n",
    "Evey substring is composed with only unique letters.\n",
    "Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: \"ABA\"\n",
    "Output: 8\n",
    "Explanation: The same as example 1, except uni(\"ABA\") = 1.\n",
    "\n",
    "Note: 0 <= S.length <= 10000.\n",
    "\n",
    "Approach:\n",
    "==========\n",
    "Find the positions of every character.\n",
    "ABA\n",
    "\n",
    "A = 0,2\n",
    "B = 1\n",
    "\n",
    "Add 0,lenght of string for all characters\n",
    "A = -1 0 2 3 \n",
    "B = -1 1 3\n",
    "\n",
    "run a loop from 1 to len-1.\n",
    "sum += (A[i]-A[i-1]) * (A[i+1]-A[i])\n",
    "\"\"\"\n",
    "import collections\n",
    "class Solution:\n",
    "    def uniqueLetterString(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        d = collections.defaultdict(list)\n",
    "        for c,v in enumerate(S):\n",
    "            d[v].append(c)\n",
    "        sum = 0 \n",
    "        for value in d.values():\n",
    "            value = [-1] + value + [len(S)]\n",
    "            for i in range(1,len(value)-1):\n",
    "                sum +=  (value[i] - value[i-1]) * (value[i+1] - value[i])\n",
    "        return sum\n",
    "\n",
    "mysol = Solution()\n",
    "print (mysol.uniqueLetterString(\"ABC\"))\n",
    "print (mysol.uniqueLetterString(\"ABA\"))\n",
    "print (mysol.uniqueLetterString(\"LETTER\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}