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❯

To count the number of substrings in a given string, we need to understand how substrings work.

What Is a Substring?

A substring is any sequence of characters that appears contiguously in the original string. For example, in the word "cat", the substrings include "c", "a", "t", "ca", "at", and "cat".

How to Count Them

For a string of length n, the total number of substrings can be found using a simple formula: n * (n + 1) / 2.

This formula works because:

From index 0, you can make n substrings
From index 1, you can make n - 1 substrings
From index 2, you can make n - 2 substrings
... and so on, down to 1

Add them up and you get: n + (n-1) + (n-2) + ... + 1 = n * (n + 1) / 2.

Case Discussion

Normal Case: If the input is "abc", it has 3 characters, so it has 3 * 4 / 2 = 6 substrings.
Single Character: If the input is "a", there's only 1 substring: "a".
All Characters Same: If the input is "aaa", substrings can still overlap: "a", "a", "a", "aa", "aa", and "aaa" — still 6 substrings in total.
Empty String: If the input string is empty (length 0), there are no substrings, so the answer is 0.

This formula gives us the count only—not the actual substrings. It’s very efficient because we don’t have to generate or store anything to get the result. The time complexity is 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

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def count_substrings(s):
    n = len(s)
    # Total substrings = n * (n + 1) // 2
    return n * (n + 1) // 2

# Example
s = "abc"
print("Total substrings:", count_substrings(s))

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