Count Number of Substrings

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

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❯

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

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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

CaseTime ComplexityExplanation
Best CaseO(1)Only a single formula is evaluated regardless of string length.
Average CaseO(1)Computation does not depend on content, just length.
Worst CaseO(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.