DP O(N) Graphic Solution with detailed explanation. Kotlin code
Firstly, let\'s think how to solve this problem WITHOUT the unique chars requirement. \nHow we should count ALL letters in all possible substrings?\nIn the tabl
Firstly, let\'s think how to solve this problem **WITHOUT** the unique chars requirement. \nHow we should count **ALL** letters in **all** possible substrings?\nIn the table below, we can see possible variants and how to count them on the string **LEETCODE**.\n\n![image](https://assets.leetcode.com/users/images/43521605-5db1-41ef-9c13-82f5d3d74e91_1652943947.6874938.png)\n\nTheoretically, we can calculate everything in **one loop**.\n\nFor the first iteration (DP[1]) we have only one option: **L**. The length of it is **1**.\nFor the second we have two options **E** and **LE**. We know that we **have added 2 letters E**, and total amount of letters will be equals to the **previous calculations + new letters amount**. \nThe previous is 1, we added 2 letters, so we have **3** for the current step.\nFor the third combination the formula remains the same: \n**PREVIOUS + NEW LETTERS** (we add **i** letters each step). Let\'s check it for **3**:\nDP=**3**(previous) + **3** (current step) = **6**. \nSo the formula is: \n**DP[i] = DP[i - 1] + i** The sum of previous + amoun of new letters.\n```\nDP[1] = L = 1\nDP[2] = E, LE = 1 + 2 = 3\nDP[3] = E, EE, LEE = 3 + 3 = 6\nDP[4] = T, ET, EET, LEET  = 6 + 4 = 10\nDP[5] = C, TC, ETC...., LEETC = 10 + 5 = 15\n```\nand so on.\n\nOkey, this problem can be easily solved with one loop and addtional array of size *string.size + 1*.\n\nNow, let\'s think about the **unique letters problem**.\nThe graphic solution looks like:\n\n![image](https://assets.leetcode.com/users/images/00d0dec7-660a-414f-903e-0243be6c4bcf_1652945569.917764.png)\n\nWhere:\nGreen - New letters: should be added to the result.\nRed - Previously counted and should be subtracted from the result.\n\nIt works in the same way, except when we met alread\u0443 added letters.\n\n```\nDP[1] = L = 1 //We have never seen L before\nDP[2] = E, LE = 1 + 2 = 3 //We have never seen E before\nDP[3] = E, EE, LEE = 3 + 3 = 6 - 2 * 2 // We HAVE SEEN E before. The previous amount of "E" was 2.\n// For this situation we should remove previous amount multiplied by 2.\n// Because we are removing it from current and from previous result. (See in the table, marked RED)\n....... // Let\'s skip the rest, because they don\'t have non unique chars\nDP[7] = 24 // Look at the table\nDP[8] = E, DE, ODE, ...., LEETCODE  = 24 + 8 -  (previous * 2 - beforePrevious)\n// As we can see from the picture, we should count only 5 new E and remove the one we count on the step 3.\nDP[8] = 24 + 8 - (3 * 2 - 2) = 24 + 8 - 4 // (marked red in the table)\nDP[8] = 28 // You can count and check it for the last row.\n```\n\nSo we can improve our formula:\n\n**DP[i] = DP[i - 1] + i - (PREV_CHAR_COUNT * 2 - BEFORE_PREV_CHAR_COUNT)** \n\nIf **we met E once** at row **2** - we will store **PREV_CHAR_COUNT  = 2**\nIf **we met E the second time** at row **3**: we will store  **PREV_CHAR_COUNT  =  3**, **BEFORE_PREV_CHAR_COUNT = 2**\n\nSo we should store TWO latest positions when we met this char before now.\n\nTo **store** it we can use something like a **HashMap<Char, Int>** \nOr if we have limited amount of Chars (A-Z) we can use an  **IntArray** with size of chats count.\n\nThe final solution looks like:\n\n```\nclass Solution {\n    fun uniqueLetterString(s: String): Int {\n        val previousStore = IntArray(28)\n        val beforePreviousStore = IntArray(28)\n        \n        val dp = IntArray(s.length + 1)\n        var sum = 0\n        for (i in 1 .. s.length) {\n            var ch = s[i-1]\n            dp[i] = dp[i-1] + i\n            \n            val previous = previousStore[ch - \'A\']\n            val beforePrevious = beforePreviousStore[ch - \'A\']\n            \n            dp[i] -= previous * 2 - beforePrevious\n            \n            beforePreviousStore[ch - \'A\'] = previous\n            previousStore[ch - \'A\'] = i\n            \n            sum += dp[i]\n        }\n        return sum\n    }\n}\n```
['Dynamic Programming', 'Kotlin']