Generate Every Non-Empty Substring with Start and End Boundaries

A substring is one unbroken stretch of the string

A substring takes characters from consecutive positions in the original string. For "abc", the valid non-empty substrings are "a", "ab", "abc", "b", "bc", and "c". The characters must stay next to each other in the original string, so "ac" is not a substring: it keeps the order but skips the character at index 1. This task considers only non-empty substrings, so the empty string is not included.

• "a" uses index 0
• "ab" uses indices 0-1
• "abc" uses indices 0-2
• "b" uses index 1
• "bc" uses indices 1-2
• "c" uses index 2

Choosing a start and an exclusive end generates every substring exactly once

Represent a substring by [start, end), where start is included and end is excluded. For "abc", start can be 0, 1, or 2. For each start, end begins at start + 1 and moves through n, which is 3. The end value 3 is valid even though the last character has index 2, because it marks the boundary immediately after the string.

The outer choice fixes where a substring begins. The inner loop extends its exclusive end one position at a time, so it produces every possible length from that start. Each pair of boundaries identifies exactly one interval, and no pair is repeated. Because the inner loop starts at start + 1, it never creates an empty interval.

The same interval needs different extraction arguments in C++ and Java

The boundary pair can stay the same in both languages, but the extraction method interprets its second argument differently. For the interval [1, 3), the substring is "bc". C++ string::substr takes the start and then the number of characters, so its second argument is 3 - 1, or 2. Java String.substring takes the start and then the exclusive end, so its second argument is 3.

string s = "abc";

for (int start = 0; start < n; start++) {
    for (int end = start + 1; end <= n; end++) {
        cout << s.substr(start, end - start) << endl;
    }
}

// [1, 3) extracts "bc":
s.substr(1, 2);

String s = "abc";

for (int start = 0; start < n; start++) {
    for (int end = start + 1; end <= n; end++) {
        System.out.println(s.substring(start, end));
    }
}

// [1, 3) extracts "bc":
s.substring(1, 3);

s.substring(1, ___);

There are six substrings, but printing them processes ten characters

The number of intervals comes from the number of choices at each start. Start 0 creates 3 substrings, start 1 creates 2, and start 2 creates 1. Their total is 3 + 2 + 1 = 6, which matches n * (n + 1) / 2 when n is 3.

Generating six intervals is one count of work, but extracting and printing them also handles the characters inside each interval. For "abc", the lengths are 1, 2, 3, 1, 2, and 1, which add up to 10 characters. In general, the number of intervals is O(n^2), while the total characters printed can be O(n^3), because long substrings are processed one character at a time.