# Find the no of substrings a character is part of

I am looking for a O(1) solution for finding the number of substrings a character is part of.

For instance, let s = "abcde" and all substrings of s are
a, b, c, d, e, ab, bc, cd, de, abc, bcd, cde, abcd, bcde, abcde

Now 'a' is part of a, ab, abc, abcd, abcde
So I guess The first (and the last character) of the string is part of 5 or in general len(s) substrings

'b' is part of b, ab, bc, abc, bcd, abcd, bcde, abcde, 8 substrings
'c' is part of c, bc, cd, abc, bcd, cde, abcd, bcde, abcde, 9 substrings

So in general how do I find the no of substrings a character in part of ?
also assume all characters are distinct.

Edit:
What I have tried so far.

Total number of substring ?
n * (n + 1) / 2, where n = len(s)

I guess its len(s) - i, where 'i' is the index (0 based indexing) of given letter ?

Also it looks like the closer a letter is to len(s) / 2, the higher its substing count

• What have you tried? This is a straightforward counting argument. Can you count how many substrings there are in the string, total? Can you count how many substrings start with the given letter? What progress have you made on this task?
– D.W.
Commented Apr 25, 2023 at 16:00
• Can you clarify on whether the original string will always have distinct characters, or are repeats allowed?
– JimN
Commented Apr 25, 2023 at 17:26
• @D.W. I have added what I have tried / found so far Commented Apr 25, 2023 at 17:28
• @JimN Assume all characters are distinct Commented Apr 25, 2023 at 17:29
• @YvesDaoust my bad, corrected Commented Apr 25, 2023 at 17:40

In your length-5 string, your indices are $$0,1,2,3,4$$.
Take a character like $$b$$ of index 1. It will be in every substring defined by $$(i,j)$$ where $$i$$ can be $$0,1$$ and $$j$$ can be any of $$1,2,3,4$$. Can you see why the answer for $$b$$ is 8 without having the write them all out?
Take character $$c$$ at position index 2. It will be in every substring starting at index $$i=0,1,2$$ and ending at index $$j=2,3,4$$. Can you see why your answer for $$c$$ is 9 without having to write them all out?