C++ Recursion + Memoization Solution
Okay, I haven\'t found a single decent recursive solution to this problem that explains how we arrived at the recurrence relation. And so I spent 3 hours on thi
Okay, I haven\'t found a single decent recursive solution to this problem that explains how we arrived at the recurrence relation. And so I spent 3 hours on this problem trying to think recursively (since that\'s what I\'m comfortable with) and here it is.\n\n#### Problem Definition\n(Consider `N = A.size()`)\n\n> `F(i) = sum of all the countUniqueChars(A[i:j]) where j >= i and j < N` \n\nIn simpler terms, we\'re basically trying to find out countUniqueChars() of all the substrings which start with `A[i]` .\nSo, the answer to our original problem is  `Sum(F(i)) where i >= 0 && i < N`\n\n#### Base Cases\n\n> `F(N) = 0` (Empty substring)\n> `F(N - 1) = 1` (Single character)\n\n#### Recurrence Relation\n\n```\n F(i) = total + F(i + 1)\n \n The tricky part is to calculate total.\n \n\t\t* If in the substring starting at i + 1 upto N - 1, we don\'t have any ocurrences of A[i], then we can take all the substrings starting at A[i] upto the last character and add the substrings we get from F(i + 1)\n\t\t\t\t=>  total = ((N - 1) - (i) + 1)\n\t\t* If the no. of ocurrences of A[i] in the substring A[i + 1: j] (j >= i + 1, j < N) is non zero\n\t\t\t* Then upto the next occurrence of A[i], we have unique substrings. So, we can keep a variable total and increment it.\n\t\t\t* Starting from the next ocurrence of A[i] (say which happens at index k), we need to decrement total since those strings should be removed from the result of F(i + 1). \n\t\t\t* Once we reach the next to next ocurrence of A[i], we stop it since going forward won\'t have any impact on the count because that would already have been accounted for in F(i + 1), i.e. the property of maintaining uniqueness in the substring.\n\nGist:  "total++" till the next ocurrence of A[i], and then we do "total--" till the next to next ocurrence of A[i] (or till we\'re < N whichever is less)\n```\n\n#### Implementation\n\nThe idea is to keep the indexes of each A[i] in a `vector<deque<int>>`. We\'re using a deque here since it allows values to be popped from the front in O(1).\n\n```\nclass Solution {\npublic:\n    vector<int> v;\n    vector<deque<int>> m;            // stores the indices of a character in string\n\n    int uniqueLetterString(string s) {\n\t     m.resize(26, deque<int>());\n        v.resize(s.size(), -1);\n        int ans = 0;\n        \n\t\t// Populate the indexes for each character\n        for(int i = 0; i < s.size(); i++)\n            m[s[i]-\'A\'].push_back(i);\n        \n        for(int i = 0; i < s.size(); i++)\n            ans += F(i, s);\n        \n        return ans;\n    }\n    \n    int F(int i, string &s) {\n        int n = s.size();\n\t\t\n\t\t// Base case\n        if (i == n)\n            return 0;\n        \n\t\t// Memoization\n        if (v[i] != -1)\n            return v[i];\n        \n\t\t// Handles the case when a single character is there in the substring starting at i\n        int total = 1;\n        \n\t\t// Since we\'re processing the ith index right now, we won\'t need this index in map afterwards\n        m[s[i]-\'A\'].pop_front();\n\t\t\n        if (m[s[i]-\'A\'].empty()) {\n\t\t\t// A[i] doesn\'t occur again in the rest of the substring (suffix substring A[i + 1:])\n            total += (n - 1) - (i + 1) + 1;\n        } else {\n\t\t\t// nextIdx is the index of the next ocurrence of A[i]. We increment total.\n            int nextIdx = m[s[i]-\'A\'].front();\n            total += (nextIdx - 1) - (i + 1) + 1;\n            \n\t\t\t// nextNextIdx is the index of the next ocurrence of A[i]\n            int nextNextIdx = n-1;\n            if (m[s[i]-\'A\'].size() >= 2) {\n                nextNextIdx = min(nextNextIdx, m[s[i]-\'A\'][1] - 1);\n            }\n            \n\t\t\t// We decrement total starting at nextIdx upto nextNextIdx\n            total -= (nextNextIdx - nextIdx + 1);\n        }\n\t\t\n        return v[i] = F(i + 1, s) + total;\n    }\n};\n```\n\n#### Complexity\n\nO(N) time and O(N) space
['Recursion', 'Memoization', 'C']