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

Getting 40 as answer. What's the answer?

---

No n(n+1)/2 will be counting many repetitive substrings..

aabbbccdd

1st a	a	aa	aab	aabb	aabbb	aabbbc	aabbbcc	aabbbccd	aabbbccdd
2nd a	a	ab	abb	abbb	abbbc	abbbcc	abbbcd	abbbccdd
1st b	b	bb	bbb	bbbc	bbbcc	bbbccd	bbbccdd
2nd b	b	bb	bbc	bbcc	bbccd	bbccdd
3rd b	b	bc	bcc	bccd	bccdd
1st c	c	cc	ccd	ccdd
2nd c	c	cd	cdd
1st d	d	dd
2nd d	d

6 sub strings are extra in n(n+1)/2 count so subtract them.

If empty string is to be considered as a substring then we add 1.

 

---

For 5 length getting 5 as answer

---

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.