Count Number of Substrings - Visualization

Strings

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❯

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❯

  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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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❯

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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...