1
$\begingroup$

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)

Number of substring that start with the given letter ?
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

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Apr 25, 2023 at 16:00
  • $\begingroup$ Can you clarify on whether the original string will always have distinct characters, or are repeats allowed? $\endgroup$
    – JimN
    Commented Apr 25, 2023 at 17:26
  • $\begingroup$ @D.W. I have added what I have tried / found so far $\endgroup$
    – Julkar9
    Commented Apr 25, 2023 at 17:28
  • $\begingroup$ @JimN Assume all characters are distinct $\endgroup$
    – Julkar9
    Commented Apr 25, 2023 at 17:29
  • 1
    $\begingroup$ @YvesDaoust my bad, corrected $\endgroup$
    – Julkar9
    Commented Apr 25, 2023 at 17:40

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Ok I got it now, thanks $\endgroup$
    – Julkar9
    Commented Apr 25, 2023 at 17:41

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.