Count substrings with same first and last character

Given a string we have check contiguous substrings with same first and last characer.

Input:
abcab

Output:
7 (a,abca,b,bcab, c, a, b)

Naive Solution: T: O(n^2) S: O(1) 

    We initialize the count to length of the string as each and every element contribute to its length. 
     In the outer loop we will pick a element. In the inner loop we will compare it other elements and if they are equal we will increment the counter. 

Code:
import java.util.*;

public class Solution {
    
    public static void main(String[] args) {
        String str = "aba";
        char[] s = str.toCharArray();
        int len = s.length;
        int count = len;
        for(int i=0; i<len-1; i++){
            for(int j=i+1; j<len; j++){
                if(s[i]==s[j]){
                    count++;
                }
            }
        }
        System.out.print(count);
        
       }
}

Output:

4

Efficient Solution: O(n) time complexity

    As we see we will see a relationship between the character count and its contribution to the substring total. 

for example consider "aaaa"
   Count = 4 (a,a,a,a) + 3(aa,aa,aa) + 2(aa,aa) +1(a) = 10
   which is (count+1)C2 => (4*5) /2 = 10
It is number of ways of selecting 2 from 4 and selecting 1 + number of selecting 1 from 3
    = 4C2 + 4C1 = (4*3/1*2) +(4/1) = (6+4) = 10


Code:

import java.util.*;

public class Solution {
    
    public static void main(String[] args) {
        
        String str = "aaaab";
        char[] s = str.toCharArray();
        int len = s.length;
        int[] freq = new int[26];
        int count = 0;
        
        for(int i=0; i<len; i++){
           freq[s[i]-'a']++;
        }
        
        for(int i=0; i<26; i++){
            int n = freq[i];
            count += (( n * (n+1) )/ 2);
        }
        System.out.print(count);
        
       }
}

Output:

11