Count Number of Substrings

Problem Statement❯

Given a string of length n, your task is to count the total number of substrings present in it.

A substring is a contiguous part of the string. For example, in the string "abc", the substrings are: "a", "b", "c", "ab", "bc", and "abc".

Note: Do not confuse substrings with subsequences. A substring maintains the original order and continuity of characters, whereas a subsequence can skip characters.

If the input string is empty, the number of substrings is 0.

Examples❯

Input String	Length (n)	Total Substrings	Description
"abc"	3	6	Substrings: a, b, c, ab, bc, abc
"abcd"	4	10	Total = 4 + 3 + 2 + 1 = 10 substrings
"a"	1	1	Only one character, one substring
"aa"	2	3	Substrings: a, a, aa
""	0	0	No characters, so no substrings

Solution❯

Understanding the Problem

We are given a string, and we need to count how many substrings it has.

A substring is a sequence of characters that occurs contiguously in the original string. For example, the string "cat" has the following substrings: "c", "a", "t", "ca", "at", and "cat".

The key idea is to find an efficient way to count all such contiguous combinations, without actually generating them.

Step-by-Step Solution with Example

Step 1: Understand what we’re trying to count

We are not counting characters or subsequences. We are counting all possible contiguous sequences within the string. That’s what makes it a substring.

Step 2: Look at patterns from small examples

Let’s take the string "abc" which has 3 characters.

Starting from index 0: "a", "ab", "abc" → 3 substrings
Starting from index 1: "b", "bc" → 2 substrings
Starting from index 2: "c" → 1 substring

Total = 3 + 2 + 1 = 6 substrings.

Step 3: Use the formula

For any string of length n, the number of substrings is:

n * (n + 1) / 2

This is because:

From index 0: n substrings
From index 1: n - 1 substrings
... down to 1

It forms an arithmetic sum: n + (n - 1) + (n - 2) + ... + 1 = n * (n + 1) / 2

Step 4: Apply it on the example

For the string "abc", n = 3

Using the formula: 3 * (3 + 1) / 2 = 3 * 4 / 2 = 6

So, the string "abc" has 6 substrings.

Edge Cases

Empty String: If the input is "", then n = 0. So, substrings = 0 * 1 / 2 = 0
Single Character: Input "a" has only one substring: "a"
All Same Characters: Input "aaa" has substrings "a", "a", "a", "aa", "aa", "aaa" → Total = 6 (overlapping substrings count)
Long Strings: Even for long strings, we can compute the count instantly without loops, since the formula is O(1)

Finally

This solution is very efficient and beginner-friendly. We don’t need to use loops or store the substrings. We only need to know the length of the input string, apply the formula n * (n + 1) / 2, and we’re done!

This approach handles all edge cases naturally, and is optimal with constant time complexity O(1).

Algorithm Steps❯

Find the length of the input string n.
Apply the formula n * (n + 1) / 2.
Return the result as the total number of substrings.

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <string.h>

int countSubstrings(char* s) {
    int n = strlen(s);
    // Total substrings = n * (n + 1) / 2
    return n * (n + 1) / 2;
}

int main() {
    char s[] = "abc";
    printf("Total substrings: %d\n", countSubstrings(s));
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	Only a single formula is evaluated regardless of string length.
Average Case	O(1)	Computation does not depend on content, just length.
Worst Case	O(1)	Even for the largest strings, only the length is used in a constant time operation.

Space Complexity❯

O(1)

Explanation: The algorithm uses a constant amount of memory for computation.

⬅ Previous TopicImplement Atoi - Convert String to Integer in Java

Next Topic ⮕Edit Distance Problem

Comments

Loading comments...