# Count substrings with same first and last characters

We are given a string S, we need to find count of all contiguous substrings starting and ending with same character.

Examples :

Input : S = "abcab"
Output : 7
There are 15 substrings of "abcab"
a, ab, abc, abca, abcab, b, bc, bca
bcab, c, ca, cab, a, ab, b
Out of the above substrings, there
are 7 substrings : a, abca, b, bcab,
c, a and b.

Input : S = "aba"
Output : 4
The substrings are a, b, a and aba

a) One approach would be to use brute force, (O(n^2)) approach where check for each substring and increment count

• What do you mean by optimal? Better than $O(n^2)$? – fade2black Nov 2 '17 at 0:24
• Yes better than brute force and preferably better than O(n^2) – MrKickass Nov 2 '17 at 0:45

You can do it in linear time. Loop over the characters of the string and count the frequency (how many times it appears in the string) of each distinct character. Then if a character has a frequency $n$ then the count of all contiguous substrings starting and ending with same character is $\frac{(n+1)n}{2}$ and finally sum up all counts.

Example 1: $abcab$.
Frequencies: $f(a)=2, f(b)=2, f(c)=1$.
Counts: $3,3,1$ which gives $7$.

Example 2: $aba$.
Frequencies: $f(a)=2, f(b)=1$.
Counts: $3,1$ which gives $4$.

Example 3: $aaa$.
Frequencies: $f(a)=3$.
Counts: $6$ which gives $6$.

Example 4: $abc$.
Frequencies: $f(a)=1, f(b)=1, f(c)=1$.
Counts: $1,1,1$ which gives $3$.

NOTE: $n*(n+1)/2$ is deduced this way:

Suppose you have this string $abcaba$ where first $a$ can be matched with second a at index 3 (0 indexed array) and also third $a$ at index 5.

frequency of $a$ is 3 so for first $a$ we will get 3-1 = 2 continuous substrings.

for second a we get 2-1 = 1 continuous substring

We are seeing a pattern as this: n,n-1, n-2.....0

This leads to the formula n*(n+1)/2 as we also need to consider individual $a$'s.

2 + 1 + 3 times $a$ = 6

Same is true for other characters in the string.

• Thank you @fade2black. Can you please explain " Then if a character has a frequency n the count of all contiguous substrings starting and ending with same character is (n+1)*n/2 including identical substrings like given in your example" this statement? – MrKickass Nov 2 '17 at 1:44
• In your first example you count the substring "a" two times. I mean you do not count distinct substrings, you count all substrings. – fade2black Nov 2 '17 at 1:48
• I removed that sentence to avoid confusions. – fade2black Nov 2 '17 at 1:53

Create a dictionary for storing number of substrings starting and ending with this character. Iterate through the string and calculate the result accordingly — for each character you know how many substrings are there already starting (and ending) with this character so you can calculate next state. Finally, you just need to sum the values.

This gives $O(n)$ if using dictionary with $O(1)$ inserts and updates.