How many substrings of non-zero length can be formed from a character string…
1998
How many substrings of non-zero length can be formed from a character string of length n?
- A.
n
- B.
n^2
- C.
2^n
- D.
n(n + 1)/2
Attempted by 94 students.
Show answer & explanation
Correct answer: D
A substring is a contiguous part of the original string. Count substrings by their length. For length 1, there are n choices. For length 2, there are n - 1 choices. In general, for length k, there are n - k + 1 substrings. Therefore the total number of non-empty substrings is n + (n - 1) + ... + 1 = n(n + 1)/2. Hence, the correct answer is n(n + 1)/2.