Divide And Conquer O(nlogn) | Java
I did not see any post covering a nice divide and conquer approach. The merge can be done in O(n) time making the total time complexity O(nlgn).\n\nThe merge co
I did not see any post covering a nice divide and conquer approach. The merge can be done in `O(n)` time making the total time complexity `O(nlgn)`.\n\nThe merge code can probably be simplified.\n```\nclass Solution {\n    private long merge(char[] arr, int lo, int hi, int mid) {\n        // To save at which index a particular character comes for the first time in the left array. \n        // Here we save index starting from the back to make further calculations easier.\n        int[] left1 = new int[26];\n        int[] left2 = new int[26];\n        \n        // To save at which index a particular character comes for the first time in the right array.\n        int[] right1 = new int[26];\n        int[] right2 = new int[26];\n        \n        int leftSize = mid - lo + 1;\n        int rightSize = hi - mid;\n        \n        Arrays.fill(right1, rightSize);  // fill with size of right array.\n        Arrays.fill(right2, rightSize);\n        Arrays.fill(left1, leftSize);   // fill with size of left array.\n        Arrays.fill(left2, leftSize);\n        \n        // fill right.\n        for (int i=mid+1 ; i<=hi ; ++i) {\n            if (right1[arr[i] - \'A\'] == rightSize) {\n                right1[arr[i] - \'A\'] = i - mid - 1;\n            } else if (right2[arr[i] - \'A\'] == rightSize) {\n                right2[arr[i] - \'A\'] = i - mid - 1;\n            }\n        }\n        \n        // fill left.\n        for (int i=mid ; i>=lo ; --i) {\n            if (left1[arr[i] - \'A\'] == leftSize) {\n                left1[arr[i] - \'A\'] = mid - i;\n            } else if (left2[arr[i] - \'A\'] == leftSize) {\n                left2[arr[i] - \'A\'] = mid - i;\n            }\n        }\n        \n        long count = 0;\n        for (int i=0 ; i<26 ; ++i) {\n            // count all substring where (char)(\'A\' + i) is taken once from the left side and zero times from\n            // the right side.\n            if (left1[i] != leftSize) {\n                count += ((left2[i] - left1[i]) * (long) right1[i]);\n            }\n            // count all substring where (char)(\'A\' + i) is taken once from the right side and zero times from\n            // the left side.\n            if (right1[i] != rightSize) {\n                count += (left1[i] * (long) (right2[i] - right1[i]));\n            }\n        }\n        \n        return count;\n    }\n    \n    private long divideAndConquer(char[] arr, int i, int j) {\n        // no characters.\n        if (j < i) return 0l;\n        // one character.\n        if (i == j) return 1;\n        // two characters.\n        if (j - i == 1) {\n            return (arr[i] == arr[j]) ? 2 : 4;\n        }\n        // three characters (this is optional but improves runtime from 340ms to 120ms).\n        if (j - i == 2) {\n            if (arr[i] == arr[i+1] && arr[i+1] == arr[i+2]) return 3;\n            if (arr[i] == arr[i+1]) return 6;\n            if (arr[i+1] == arr[i+2]) return 6;\n            if (arr[i] == arr[i+2]) return 8;\n            return 10;\n        }\n        \n        int mid = i + (j - i) / 2;\n        long left = divideAndConquer(arr, i, mid);\n        long right = divideAndConquer(arr, mid + 1, j);\n        long combine = merge(arr, i, j, mid);\n        return left + right + combine;\n    }\n    \n    public int uniqueLetterString(String s) {\n        char[] arr = s.toCharArray();\n        int len = arr.length;\n        return (int) divideAndConquer(arr, 0, len - 1);\n    }\n}\n```
['Divide and Conquer', 'Java']