Number of subsequences of the form a^i b^j c^k.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Given a string, count number of subsequences of the form aibjck, i.e., it consists of i ’a’ characters, followed by j ’b’ characters, followed by k ’c’ characters where i >= 1, j >=1 and k >= 1.\n",
    "\n",
    "Note: Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.\n",
    "\n",
    "Expected Time Complexity : O(n)\n",
    "\n",
    "Examples:\n",
    "\n",
    "Input  : abbc\n",
    "Output : 3\n",
    "Subsequences are abc, abc and abbc\n",
    "\n",
    "Input  : abcabc\n",
    "Output : 7\n",
    "Subsequences are abc, abc, abbc, aabc\n",
    "abcc, abc and abc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "We traverse given string. For every character encounter, we do following:\n",
    "\n",
    "1) Initialize counts of different subsequences caused by different combination of ‘a’. Let this count be aCount.\n",
    "\n",
    "2) Initialize counts of different subsequences caused by different combination of ‘b’. Let this count be bCount.\n",
    "\n",
    "3) Initialize counts of different subsequences caused by different combination of ‘c’. Let this count be cCount.\n",
    "\n",
    "4) Traverse all characters of given string. Do following for current character s[i]\n",
    "    If current character is ‘a’, then there are following possibilities :\n",
    "    a) Current character begins a new subsequence.\n",
    "    b) Current character is part of aCount subsequences.\n",
    "    c) Current character is not part of aCount subsequences.\n",
    "    Therefore we do aCount = (1 + 2 * aCount);\n",
    "\n",
    "    If current character is ‘b’, then there are following possibilities :\n",
    "    a) Current character begins a new subsequence of b’s with aCount subsequences.\n",
    "    b) Current character is part of bCount subsequences.\n",
    "    c) Current character is not part of bCount subsequences.\n",
    "    Therefore we do bCount = (aCount + 2 * bCount);\n",
    "\n",
    "    If current character is ‘c’, then there are following possibilities :\n",
    "    a) Current character begins a new subsequence of c’s with bCount subsequences.\n",
    "    b) Current character is part of cCount subsequences.\n",
    "    c) Current character is not part of cCount subsequences.\n",
    "    Therefore we do cCount = (bCount + 2 * cCount);\n",
    "\n",
    "5) Finally we return cCount;\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# Python 3 program to count \n",
    "# subsequences of the form \n",
    "# a^i b^j c^k \n",
    "\n",
    "# Returns count of subsequences \n",
    "# of the form a^i b^j c^k \n",
    "def countSubsequences(s): \n",
    "\n",
    "    # Initialize counts of different \n",
    "    # subsequences caused by different \n",
    "    # combination of 'a' \n",
    "    aCount = 0\n",
    "\n",
    "    # Initialize counts of different \n",
    "    # subsequences caused by different \n",
    "    # combination of 'a' and different \n",
    "    # combination of 'b' \n",
    "    bCount = 0\n",
    "\n",
    "    # Initialize counts of different \n",
    "    # subsequences caused by different \n",
    "    # combination of 'a', 'b' and 'c'. \n",
    "    cCount = 0\n",
    "\n",
    "    # Traverse all characters \n",
    "    # of given string \n",
    "    for i in range(len(s)): \n",
    "    \n",
    "        # If current character is 'a', \n",
    "        # then there are following \n",
    "        # possibilities : \n",
    "        #     a) Current character begins \n",
    "        #     a new subsequence. \n",
    "        #     b) Current character is part \n",
    "        #     of aCount subsequences. \n",
    "        #     c) Current character is not \n",
    "        #     part of aCount subsequences. \n",
    "        if (s[i] == 'a'): \n",
    "            aCount = (1 + 2 * aCount) \n",
    "\n",
    "        # If current character is 'b', then \n",
    "        # there are following possibilities : \n",
    "        #     a) Current character begins a \n",
    "        #     new subsequence of b's with \n",
    "        #     aCount subsequences. \n",
    "        #     b) Current character is part \n",
    "        #     of bCount subsequences. \n",
    "        #     c) Current character is not \n",
    "        #     part of bCount subsequences. \n",
    "        elif (s[i] == 'b'): \n",
    "            bCount = (aCount + 2 * bCount) \n",
    "\n",
    "        # If current character is 'c', then \n",
    "        # there are following possibilities : \n",
    "        #     a) Current character begins a \n",
    "        #     new subsequence of c's with \n",
    "        #     bCount subsequences. \n",
    "        #     b) Current character is part \n",
    "        #     of cCount subsequences. \n",
    "        #     c) Current character is not \n",
    "        #     part of cCount subsequences. \n",
    "        elif (s[i] == 'c'): \n",
    "            cCount = (bCount + 2 * cCount) \n",
    "\n",
    "    return cCount \n",
    "\n",
    "# Driver code \n",
    "if __name__ == \"__main__\": \n",
    "    s = \"abcbc\"\n",
    "    print(countSubsequences(s)) \n",
    "\n",
    "# This code is contributed \n",
    "# by ChitraNayal \n"
   ]
  },
  {
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}