[Java] explanation with simple O(N) solution, no DP
Problem Statement:\n Return the total number of unique characters in every substring of a string s\n \nIntuition:\n We can immediately think about breaking the 
**Problem Statement:**\n Return the total number of unique characters in every substring of a string ```s```\n \n**Intuition:**\n We can immediately think about breaking the problem down in terms of a DP approach, though using DP isn\'t necessary at all.\n \n If we want to find the total # of unique characters in every substring of ```s```, we can deconstruct the problem into:\n```\n Find the total number of unique characters in every substring ending at position 0\n +\n Find the total number of unique characters in every substring ending at position 1\n +\n ... so on and so forth\n```\n\nSince we\'ve framed the problem in that way, it\'s really easy to get stuck fixating on ideas revolving around calculating the number of unique characters for every substring ending at index `i`.\n\nWhile this is an absolutely valid thought, it actually feels a bit easier to think about it in the perspective of each **letter**, not each substring. In other words, for some index `i`:\n**Instead of**\n"how many characters are unique in the substring (0, i)?"\n"how many characters are unique in the substring (1, i)?"\n...\n"how many characters are unique in the substring (i - 1, i)?"\n\n**Think of it as**\n"char `a` is unique in how many substrings ending at index `i`?"\n"char `b` is unique in how many substrings ending at index `i`?"\n...\n"char `z` is unique in how many substrings ending at index `i`?"\n\nLet\'s explore this idea.\n\nWe know that a character is unique if it is present **exactly once** in a substring. As soon as it appears one more time, it is no longer unique and no longer counts to the total.\n\nWe can use this intuition to realize that however long our substring is, a character will be counted as unique once it appears in a substring, and will stop being counted once it appears a second time in a substring. Does that make sense? If you have the word "DEER" and we are at position R looking backwards, as soon as we hit the \'second\' E (E at index 1), we don\'t even have to think twice about the rest of the string- we know E will forever remain non-unique. This means all we need to do is find the distance between a letter\'s most recent occurrence, and second most recent occurrence. The distance between those values will indicate how many times that letter appears uniquely for all substrings ending at some position `i`. If we do this for all 26 letters and add them up, we get the total number of unique characters in all substrings ending at position `i` in the array. Do this for every position in the array, and we have our final answer.\n\nAs an example:\n`String s = "METAMORPHOSIS", idx = 10`\nSay we are at index 10 (the first S) trying to calculate the # of unique characters for all substrings ending with that position. Here are all of those substrings, starting from the smallest.\n```\n"S"\n"OS"\n"HOS"\n"PHOS"\n"RPHOS"\n"ORPHOS"\n"MORPHOS"\n"AMORPHOS"\n"TAMORPHOS"\n"ETAMORPHOS"\n"METAMORPHOS"\n```\n\nNow, for every letter we want to find the total number of times it uniquely occurs in all of these substrings.\n\nLet\'s start with the letter `A`. How can we tell how many times A appears uniquely? Well first we need to know the **most recent** time it appears (most recent means closest to our `idx`). And then we need to know the **second most recent** time it appears. `A` appears most recently from index 10 at index 3 and doesn\'t appear again . \n\nThis means A is unique for all substrings that start at or before index 3. There are four substrings for which this is the case, the ones starting at indices [0, 1, 2, 3]. \nA appears uniquely 4 times, so we can add that to our global count.\n\nThe next letter in the alphabet that appears in `s` is letter `E`. When is it\'s most recent appearance? index 1. It also does not have a second most recent appearance, therefore E is unique for all substrings that start at or before index 1, i.e. indices [0, 1]. We add 2 to our global count.\n\nLet\'s jump to the letter `M` now. It\'s most recent appearance is at index 4. It also happens to have a second most recent appearance at index 0. What does this mean? Previously our letters only occurred once, which meant they were unique in every substring that contained index `idx`- AKA all the substrings that started at or before `idx`. But now that a second `M` appeared, it is only unique in substrings starting at `index <= 4 AND index > 0`,  indices [1, 2, 3, 4] (we exclude 0 since that was the index of the second appearance of `M`). We can now add 4 to our global count, representing the # of times `M` appears exactly once for all substrings ending at index `idx`.\n\nIf we do this for each letter of the alphabet, we get the total amount of characters that appear uniquely in substrings ending at index `idx`.\n\n**Implementation**\nAll we need to do is keep two arrays- one to track the most recent appearance of each letter, and one to track the second most recent appearance.\nThen, for each position in the string, we iterate through the 26 indices in those arrays, and add their difference to our global sum. Their difference represents the amount of substrings that exist containing exactly 1 appearance of the character at that array index.\n\nThis results in a runtime of O(26 * N)  = **O(N)**.\n\n\n```\nclass Solution {\n    public int uniqueLetterString(String s) {\n        int total = 0;\n        \n\t\t// Initialize our most-recent and second-most-recent arrays\n        int[] l1 = new int[26];\n        int[] l2 = new int[26];\n        Arrays.fill(l1, -1);\n        Arrays.fill(l2, -1);\n        \n\t\t// Iterate through every position in String s\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n\t\t\t// Update the arrays with the new char\n            l2[c - \'A\'] = l1[c - \'A\'];\n            l1[c - \'A\'] = i;\n            \n\t\t\t// Add the difference between the most-recent index and second-most-recent index of every letter to the global total\n            for (int j = 0; j < l1.length; j++) {\n                total += (l1[j] - l2[j]);\n            }\n        }\n        \n        return total;\n    }\n}\n```\n\nHope this helps!
['Java']