Count Number of Substrings in a String

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.

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).

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.

#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;
}

#include <iostream>
#include <string>
using namespace std;

int countSubstrings(const string& s) {
    int n = s.length();
    // Total substrings = n * (n + 1) / 2
    return n * (n + 1) / 2;
}

int main() {
    string s = "abc";
    cout << "Total substrings: " << countSubstrings(s) << endl;
    return 0;
}

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))

public class SubstringCounter {
    public static int countSubstrings(String s) {
        int n = s.length();
        // Total substrings = n * (n + 1) / 2
        return n * (n + 1) / 2;
    }

    public static void main(String[] args) {
        String s = "abc";
        System.out.println("Total substrings: " + countSubstrings(s));
    }
}

function countSubstrings(s) {
    const n = s.length;
    // Total substrings = n * (n + 1) / 2
    return (n * (n + 1)) / 2;
}

const s = "abc";
console.log("Total substrings:", countSubstrings(s));

package main

import (
    "fmt"
)

func countSubstrings(s string) int {
    n := len(s)
    // Total substrings = n * (n + 1) / 2
    return n * (n + 1) / 2
}

func main() {
    s := "abc"
    fmt.Println("Total substrings:", countSubstrings(s))
}

fn count_substrings(s: &str) -> usize {
    let n = s.len();
    // Total substrings = n * (n + 1) / 2
    n * (n + 1) / 2
}

fn main() {
    let s = "abc";
    println!("Total substrings: {}", count_substrings(s));
}

fun countSubstrings(s: String): Int {
    val n = s.length
    // Total substrings = n * (n + 1) / 2
    return n * (n + 1) / 2
}

fun main() {
    val s = "abc"
    println("Total substrings: ${countSubstrings(s)}")
}

func countSubstrings(_ s: String) -> Int {
    let n = s.count
    // Total substrings = n * (n + 1) / 2
    return n * (n + 1) / 2
}

let s = "abc"
print("Total substrings: \(countSubstrings(s))")

function countSubstrings(s: string): number {
    const n = s.length;
    // Total substrings = n * (n + 1) / 2
    return (n * (n + 1)) / 2;
}

const s = "abc";
console.log("Total substrings:", countSubstrings(s));

Time complexity

Space complexity

O(1)

The algorithm uses a constant amount of memory for computation.