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
Please suggest optimal solutions

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

3 Answers 3


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.

  • $\begingroup$ 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? $\endgroup$
    – MrKickass
    Nov 2, 2017 at 1:44
  • $\begingroup$ In your first example you count the substring "a" two times. I mean you do not count distinct substrings, you count all substrings. $\endgroup$
    – fade2black
    Nov 2, 2017 at 1:48
  • $\begingroup$ I removed that sentence to avoid confusions. $\endgroup$
    – fade2black
    Nov 2, 2017 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.


public static int countSubstrs (String str, int i, int j, int n) {

if (n == 1) {

return 1;

if (n <= 0) {

return 0;

int res =   countSubstrs (str, i + 1, j, n -1) +

              countSubstrs(str, i, j-1, n-1) -

               countSubstrs (str, i + 1, j-1, n-2);

if (str.charAt(i) == str.charAt(j)) {

return res;


  • 1
    $\begingroup$ We're not a coding site, and we're not looking for answers that consist of a block of code. Instead, we're looking for ideas, explanations, concise pseudocode, justifications of correctness. I encourage you to edit your answer to explain the ideas and why your proposed solution works. Also, please edit your answer to correct the formatting. $\endgroup$
    – D.W.
    Oct 2, 2022 at 5:22
  • $\begingroup$ Muse about how many operations your suggestion requires for a string of length 3, 4, 5, 6, 12, n. $\endgroup$
    – greybeard
    Oct 2, 2022 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.