Number of sub-strings for a given sub string having repeated symbols

Question

Lets for a a given string aabbbccdd

I need to find the number of substrings possible how to go about it? Does the n(n+1)/2 formula work here also?

Comments

For 3 length getting 7. You are missing some

---

@Mayank Gupta 3

Thanks..I missed the 3rd b..added now..

---

The answer is 40 but I wanted to know the working.

Answer 1

(SUBSTRING: IS CONTIGUOUS SEQUENCE OF CHARACTERS OF A STRING  )

We know :  general formula to find number of sub strings  for given string (unique symbols) is : n*(n+1)/2 .

But, for the strings containing duplicates. Here's the way you can solve it.

First: Number of substrings with length 0 : 1

Second: Number of substrings with length 1: 4     { 'a', 'b' , 'c' , 'd' }

Now the problem arises for the substrings of length 2 and more.... 

 

let's consider a a b b b c c d d as position 1 2 3 4 5 6 7 8 9.

Substring of length 2, 3 , 4... will be created by choosing two points (positions).

E.g: a a b b b c c d d

       1 2 3 4 5 6 7 8 9   for length 2 : 1-2   2-3    3-4    4-5.....are selected i.e aa ab ... bb bb bc cc....

                      similarly for length 3:   1-3  2-4   3-5.... are selected i.e aab abb bbb....

so, you can see we just have to choose any two positions i and j and find number of combinations i.e 9C2

but we must have to remove dublicate substrings also... which is created by bb and bb only (i.e postion 3-4 and 4-5 only)

so Answer is 1 + 4 + (9C2-1)  = 1 + 4 + 35 = 40

Comments

By finding the combinations and removing the duplicates we'll get the substrings but why do we subtract 1 from the combinations ?

In answer= 1+4+(9C2 -1).

Here we're subtracting 1 from 9C2 but why

---

subtracting for the one duplicate combination “bb”
9c2 means two values ,sub-strings' lower and upper bound (with values not equal to each other).
like (1,2),(1,3),(2,5)...and so .

---

See, you have already given the answer! “By finding the combinations and removing the duplicates we'll get the substrings”, so here after we find all the possible combinations, we are getting one duplicate substring which is created by ‘bb’ and ‘bb’ only (i.e postion 3-4 and 4-5). Therefore, we have to remove any one ‘bb’, so we subtract a 1.