finding substrings of a string

algorithm math combinations
Chander Shivdasani picture Chander Shivdasani · Sep 14, 2012 · Viewed 26.9k times · Source

For a string of length n, the formula to compute all the substrings are: n(n+1)/2 Can someone help me out in intuitively understanding this formula?

Wikipedia says: "The number of substrings of a string of length where symbols only occur once, is the number of ways to choose two distinct places between symbols to start/end the substring"

Answer

user586399 picture user586399 · Sep 14, 2012

To understand this, note that any substring needs two parameters: start index and end index.

For example: string str = "Hello World"; // length == 11

Lets begin by taking only one-character substring at time: H, e, l, l, o, , W, o, r, l, d. Then by taking 2 characters at time: He, el, ll, lo, o , W, Wo, or, rl, ld. Then by taking 3 chars: Hel, .. etc.

So the total substring count is 11 + 10 + 9 + .. + 1 and, in general, for i from 1 to n, we have n - i + 1 substrings. By summition:

Sigma (n + 1 - i) from i = 1 to n, yields n * (n + 1) - n * (n + 1) / 2 which is n * (n + 1) / 2

Related questions

Creating all possible k combinations of n items in C++

There are n people numbered from 1 to n. I have to write a code which produces and print all different combinations of k people from these n. Please explain the algorithm used for that.

Read More
counting combinations and permutations efficiently

I have some code to count permutations and combinations, and I'm trying to make it work better for large numbers. I've found a better algorithm for permutations that avoids large intermediate results, but I still think I can do better …

Read More
How many different possible ways can persons be seated in a round table?

I am developing an algorithm and am looking at a possibility of the maximum number of iterations before arriving at a conclusion. In real world, it is similar to the Classical Round Table seating problem. Can you please tell me …

Read More