C# solution (Cartesian Product)
Similar problems\n\n- 1588 Sum of All Odd Length Subarrays\n- 907 Sum of Subarray Minimums\n- 828 Count Unique Characters of All Substrings of a Given String\n\
**Similar problems**\n\n- 1588 Sum of All Odd Length Subarrays\n- 907 Sum of Subarray Minimums\n- 828 Count Unique Characters of All Substrings of a Given String\n\n**Intuition**\nCartesian product of two sets A and B, denoted A X B, is the set of all ordered pairs (a, b) where a is in A and b is in B.\n![image](https://assets.leetcode.com/users/images/07588e8b-2bd7-4afb-9b57-b0145922fea7_1648770707.5255227.png)\n\nCartesian product can be used to solve a type of problems: find the number of subarrays such that every subarray has an unique element. \n\nFor example, how can we find the number of non-empty subarrays of \u201CXXXAXXXAXXXAXXX\u201D, such that each subarray contains exactly one A? \n\nWe have two options. One option is find all the subarrays first, then flush out the invalid ones by checking if there is exactly one A. The other option is find all the subarrays that each unique A belongs. \n\nOption one needs a lot of duplicated calculations, while option two will reduce the calculations by performing a batch-like process: find all the valid subarray for a given A at once.\n\nNow let try to find the number of subarrays that contain the second A: XXXAXXXAXXXAXXX. The idea is we start with the second A, then build the subarrays by extending the second A to the left and right. Whenever we find another A on either side, then the extension stops on that side. At the end, the extension process stops at \u2018(\u2019 and \u2018)\u2019: XXXA(XXXAXXX)AXXX.\n\nNow (XXXAXXX) can be divided as two sets: A = [XXXA], B = [AXXX]. Now we can use Cartesian production to calculate the number of subarrays that has A: Count(A) * Count(B). One question is what if we pick A from the both sets? In this case, the subarray is A itself. \n\nBelow is way to proof the Cartesian product result.\n![image](https://assets.leetcode.com/users/images/61f4f4f6-670c-4404-ae49-3f19cca2f369_1648771097.6067376.png)\n\n\n\n**Complexity**\n- Time: O(n)\n- Space: O(n)\n\n**Implementation**\n```\npublic class Solution {\n    public int UniqueLetterString(string s) {\n        \n        int n = s.Length;\n        \n        int[] occured = new int[26];   // last index where a given character ocurred\n        int[] leftPos = new int[n];  // leftPos[i]: from left to right, the last index where s[i] occured        \n        int[] rightPos = new int[n]; // rightPos[i]: from right to left, the last index where s[i] occured \n           \n        Array.Fill(occured, -1);    // -1 indicates the character didn\'t occur\n        Array.Fill(leftPos, -1);  // -1 indicates the character didn\'t occur on i\'s left\n        Array.Fill(rightPos, -1); // -1 indicates the character didn\'t occur on i\'s right\n        \n        for(int i = 0; i < n; i++)\n        {\n            if(occured[s[i] - \'A\'] != -1)\n                leftPos[i] = occured[s[i] - \'A\'];\n            occured[s[i] - \'A\'] = i;\n        }\n        \n        Array.Fill(occured,-1);\n        for(int i = n-1; i >= 0; i--)\n        {\n            if(occured[s[i] - \'A\'] != -1)\n                rightPos[i] = occured[s[i] - \'A\'];\n            occured[s[i] - \'A\'] = i;\n        }\n        \n        int res = 0;\n        for(int i = 0; i < n; i++)\n        {\n            int leftBoundry = leftPos[i] == -1? 0 : leftPos[i] + 1;\n            int rightBoundry = rightPos[i] == -1? n - 1 : rightPos[i] - 1;\n            \n            // Cartesian product\n            res += (i - leftBoundry + 1) * (rightBoundry - i + 1);\n        }\n        \n        return res;\n    }\n}\n```\n\nSame idea, but the implmentation is simplier\n```\npublic class Solution {\n    public int UniqueLetterString(string s) {\n        \n        if(string.IsNullOrEmpty(s))\n            throw new ArgumentException("Invalid Input.");\n        \n        int[,] prev = new int[26,2];\n        for(int i = 0; i < 26; i++)\n        {\n            prev[i,0] = -1; // last time a character occurs\n            prev[i,1] = -1; // second last time a character occurs\n        }\n\n        int res = 0;\n        for(int i = 0; i < s.Length; i++)\n        {\n            int idx = s[i] - \'A\';            \n            int secondLast = prev[idx,0]; // left boundary\n            int last = prev[idx,1];  // mid character\n            int curr = i; // right boundary\n            res += (last - secondLast) * (curr - last);\n            \n            prev[idx,0] = last;\n            prev[idx,1] = curr;\n        }\n        \n        // add the substrings that have last occurrence as the mid character\n        int n = s.Length;\n        for(int i = 0; i < 26; i++)\n        {            \n            int secondLast = prev[i,0];\n            int last = prev[i,1];\n            int curr = n;\n            \n            res += (last - secondLast) * (curr - last);\n        }\n        \n        return res;\n    }\n}\n```
[]