Java Programs›Strings›Find All Substrings of a String

Find All Substrings of a String in Java

intermediate· Strings · String Manipulation

Problem

A substring is any contiguous run of characters taken from a string — a string of length n has exactly n(n+1)/2 possible substrings.

Given a string, generate every one of its contiguous substrings.

Input

abc

Output

a, ab, abc, b, bc, c

Java Program

Java

public class FindAllSubstrings {
    public static void main(String[] args) {
        String str = "abc";
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < str.length(); i++) { // i is the starting index of each substring
            for (int j = i + 1; j <= str.length(); j++) { // j is the ending index (exclusive), so every substring has at least one character
                if (result.length() > 0) result.append(", "); // separator before every substring except the first
                result.append(str.substring(i, j));
            }
        }

        System.out.println(result.toString());
    }
}

▶ Run Code

Output

a, ab, abc, b, bc, c

Core Logic

Trying every possible starting index paired with every possible ending index generates every contiguous run of characters exactly once.

How It Works

1The outer loop picks a starting index i from 0 to str.length() - 1.
2The inner loop picks an ending index j from i + 1 up to str.length(), so the substring always has at least one character.
3str.substring(i, j) extracts the substring running from i up to, but not including, j.
4Each substring found is appended to a result buffer, separated by commas.

For "abc", starting index 0 produces "a", "ab", and "abc"; starting index 1 produces "b" and "bc"; starting index 2 produces "c".

💡

Key Point: There are O(n²) substrings in total, but copying each one costs time proportional to its own length — so the total character-copying work sums to O(n³), not O(n²), even though only n² substrings exist.

Complexity

Time Complexity: O(n³)Space Complexity: O(n³)

Why: There are O(n²) substrings in total, and copying each one costs time proportional to its own length, so the total character-copying work — and the size of the combined result — sums to O(n³).

Key Concepts

nested for loopString.substring()StringBuilder

Approach 2: Java 8

Java

import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class FindAllSubstringsStream {
    public static void main(String[] args) {
        String str = "abc";
        // flatMap() flattens one inner stream of substrings per starting index into a single stream
        String result = IntStream.range(0, str.length())
            .boxed()
            .flatMap(i -> IntStream.rangeClosed(i + 1, str.length())
                .mapToObj(j -> str.substring(i, j)))
            .collect(Collectors.joining(", "));
        System.out.println(result);
    }
}

▶ Run Code

Output

a, ab, abc, b, bc, c

Core Logic

The same pair of nested loops can be expressed as nested streams — an outer stream of starting indices, flat-mapped into an inner stream of substrings for each one.

How It Works

1IntStream.range(0, str.length()).boxed() produces every possible starting index as a stream.
2.flatMap(i -> ...) replaces each starting index with its own inner stream of substrings, flattening all of them into one combined stream.
3The inner IntStream.rangeClosed(i + 1, str.length()).mapToObj(j -> str.substring(i, j)) generates every substring starting at i, same as the loop version's inner loop.
4.collect(Collectors.joining(", ")) joins every substring from the flattened stream into the final result.

For "abc", flatMap() expands starting index 0 into "a", "ab", "abc", index 1 into "b", "bc", and index 2 into "c" — flattened into one stream in the same order as the nested loops.

💡

Key Point: flatMap() is what turns 'a stream of streams' (one inner stream per starting index) into a single flat stream — without it, the result would be a stream of streams instead of a stream of substrings.

Complexity

Time Complexity: O(n³)Space Complexity: O(n³)

Why: The nested streams still generate the same O(n²) substrings, each copied at a cost proportional to its length, so the total work is the same O(n³) as the manual loops.

Key Concepts

StreamflatMap()IntStream

← Previous

Find All Subsequences of a String

Find Character Frequency

Related Programs

Check Palindrome String

Stringsintermediate

Check Pangram

Stringsbeginner

Check String Contains Only Alphabets