Sum of unique characters of all substrings of a string

Given a String s of length of N.Find the sum of unique characters of each sub string of the given string.Each String consists of n*(n+1)/2 sub strings.

Examples :

Input :
n = 4
s = "aabb"
substrings and unique characters
a(1)
a(1)
b(1)
b(1)
aa(1)
ab(2)
bb(1)
aab(2)
abb(2)
aabb(2)
sum of unique characters of each substring =14
Output : 14

Input :
n = 3
s = "abc"
Output : 10

Naive Approach :

The idea is to find each sub string of given string and find the number of unique characters in each substring starting at i and ending at j and calculate the sum of unique characters of each sub string.

Below is the implementation of above approach :

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
class Main {
    // This Function return the sum of unique characters of
    // each substring of given string
    public static int uniqueSum(String s, int n)
    {
        // Base case
        if (n == 0)
            return 0;
        // To find the sum
        int sum = 0;

        for (int i = 0; i < n; i++) {
            // To keep track of unique chars in substring
            HashSet<Character> set = new HashSet<>();
            for (int j = i; j < n; j++) {
                // Count unique characters in subtrings
                // starting at i and ending j
                set.add(s.charAt(j));
                // Add to sum
                sum += set.size();
            }
        }
        // Return sum
        return sum;
    }

    // Driver Code
    public static void main(String[] args)
    {
        int n = 4;
        String s = "aabb";
        System.out.println(uniqueSum(s, n));
    }
}

14

Time Complexity : O(N²)

Space Complexity : O(N)

Efficient Approach :

The idea is count the contribution of each character of string in the sum of unique characters of sub strings.Number of sub strings formed including i^th  character is (i+1)*(n-i) where n is length of string.But to find current character count in  the sum we need to find number of sub strings not including last occurrence of current character.

Time Complexity : O(N)

Space Complexity : O(N)

Below is the implementation of above approach :

/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
class Main {
    // This Function return the sum of unique characters of
    // each substring of given string
    public static int uniqueSum(String s, int n)
    {
        // Base case
        if (n == 0)
            return 0;
        // To find the sum
        int sum = 0;
        // To find last ocuurence of current char
        int last[] = new int[27];
        // Initialise with -1
        Arrays.fill(last, -1);
        for (int i = 0; i < n; i++) {
            // Find number of substrings including ith
            // character not including it's last occurence
            char c = s.charAt(i);
            int left = i - last[c - 'a'];
            int right = n - i;
            sum += (left * right);
            // Update last occurence
            last[c - 'a'] = i;
        }
        // Return sum
        return sum;
    }

    // Driver Code
    public static void main(String[] args)
    {
        int n = 4;
        String s = "aaab";
        System.out.println(uniqueSum(s, n));
    }
}

13