Providing Brute Force O(n^3) and O(n^2) solution - Seeking for weak hire :)
I do not know how we can come up the best solution in an interview, especially for the hard level problem I have never seen, probably weak hire is good enough f
I do not know how we can come up the best solution in an interview, especially for the hard level problem I have never seen, probably weak hire is good enough for me...(Being super smart in interview is too hard)\n\n---\n**O(n^3) Brute Force Solution**\nThis is pretty straightforward, we just need to 2 pointers i and j which represents the start and end index of the substring. Then we just put into the map(key is the character, value is the frequency), scan through the map to find the # of unique characters(i.e. whose value is 1).\n\n**Final Code**\n```java\nclass Solution {\n    Map<String, Integer> memo = new HashMap<>();\n    public int uniqueLetterString(String s) {\n        int res = 0;\n        \n        int n = s.length();\n        for(int i = 0; i < n; i++){\n            for(int j = i + 1; j <= n; j++){\n                String substr = s.substring(i, j);\n                int cnt = countUniqChars(substr);\n                res += cnt;\n            }\n        }\n        \n        return res;\n    }\n    \n    public int countUniqChars(String str){\n        if(memo.containsKey(str)) return memo.get(str);\n        \n        int[] map = new int[26];\n        for(char c : str.toCharArray()){\n            map[c - \'A\']++;\n        }\n        \n        int res = 0;\n        for(int i = 0; i < 26; i++){\n            res += map[i] == 1 ? 1 : 0;\n        }\n        memo.put(str, res);\n        return res;\n    }\n}\n```\n\n---\n**Final O(n^2) Solution**\nThis solution comes after I finished the brute force and trying to improve the time complexity. I observe that: if the start index is fixed, then the character-frequency map can be reused as the end index increasing. We just need to push the new letter into the map, update the frequency. Instead of the going through all the maps once every we push a new character. We can just take the count of characters whose frequency is 1. It can saves lot of time. For example:\n```\nIf start index = 0 \n"LEETCODE"\n j -> Map: [L: 1], uniq cnt = 1 whose freq is 1, because we have L as a new unique; \n   j -> Map: [L: 1, E:1], uniq cnt = cnt + 1 = 2 because we have E as new unique;\n   j -> Map: [L:1, E:2], uniq cnt = cnt - 1 = 1 because we lost E as unique;\n    ...\n```\n\n**Code**\n```java\nclass Solution {\n    public int uniqueLetterString(String s) {\n        int res = 0;\n        \n        int n = s.length();\n        for(int i = 0; i < n; i++){\n            int cnt = 0;\n\t\t\t\n\t\t\t// the map is reused and shared by the substring starting from index i below\n            int[] map = new int[26];\n            for(int j = i; j < n; j++){\n                map[s.charAt(j) - \'A\']++;\n                if(map[s.charAt(j) - \'A\'] == 1) cnt++; # we are having a new unique characaters\n                else if(map[s.charAt(j) - \'A\'] == 2) cnt--; # The freq becomes 2 after we do ++, so means we lost an uniq characters\n                res += cnt;\n            }\n        }\n        \n        return res;\n    }\n```\n\n---\n**Complexity Analysis**\n**Time Compelxity**\nFor substring with starting index 0, end index went though from 0 to n - 1 -> O(n)\nFor substring with starting index 1, end index went though from 1 to n - 1 -> O(n - 1)\nFor substring with starting index 0, end index went though from 2 to n - 1 -> O(n - 2)\n....\nFor substring with starting index n - 2, end index went though from n - 2 to n - 1 -> O(2)\nFor substring with starting index n - 1, end index went though from n - 1 to n - 1 -> O(1)\nO(n + n - 1 + n - 2 + ... + 2 + 1) = O(n ^ 2)\nSo **time complexity is O(n ^ 2)**\n\n**Space Complexity**\nWe are using a map with fix size 26, so O(26) = O(1), **space complexity is O(1)**\n
[]