Java – Find all Possible Substrings of a String

A substring is a continuous sequence of characters taken from a string. For example, the string "abc" has the non-empty substrings "a", "b", "c", "ab", "bc", and "abc".

To find all possible substrings in Java, use two loops to choose the substring boundaries and call String.substring(beginIndex, endIndex). The starting index is inclusive, while the ending index is exclusive.

In this tutorial, we shall write Java programs to find all possible substrings of a string, print them directly, and collect only unique substrings when the source string contains repeated characters.

How Java substring() Uses Start and End Indexes

Java’s substring() method can extract a substring when its starting and ending positions are known. For a string str, the following expression starts at start and continues up to, but does not include, end.

</>
Copy
str.substring(start, end)

For example, if str is "apple", then str.substring(1, 4) returns "ppl". Index 1 is included and index 4 is excluded.

All Substrings of a String using Nested For Loop

One way to generate every non-empty substring is to vary the substring length from 1 through the length of the string. For each length, move the starting index from the beginning of the string to the last position where a substring of that length can start.

Algorithm to Generate Every Non-Empty Substring

The following steps describe the approach used in the Java program below.

  1. Start with the input string str.
  2. Create an empty list named allSubstrings.
  3. Set the substring length len to 1.
  4. Continue while len <= str.length().
  5. For the current length, start index at 0.
  6. Continue while index <= str.length() - len.
  7. Extract str.substring(index, index + len) and add it to the list.
  8. Increment index and repeat for the current substring length.
  9. Increment len and repeat until every length has been processed.
  10. Print or otherwise use the collected substrings.

Example.java

</>
Copy
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * Java Program - All Substrings
 */

public class Example {

	public static void main(String[] args) {

		String str = "apple";
		
		List<String> allSubstrings = new ArrayList<String>();
		
		for(int len=1; len<=str.length(); len++) { //length of substring
			for(int index=0;index<=str.length()-len;index++) { //traverse along substring
				allSubstrings.add(str.substring(index, index+len));
			}
		}
		
		System.out.println(Arrays.toString(allSubstrings.toArray()));		
	}

}

Output

[a, p, p, l, e, ap, pp, pl, le, app, ppl, ple, appl, pple, apple]

The output contains two occurrences of "p" because "apple" contains p at two different positions. This version generates substrings by position, so equal text obtained from different positions is retained.

Print All Java Substrings Without Storing Them in a List

If the goal is only to print each substring, there is no need to store every value in an ArrayList. The substring can be printed as soon as its start and end indexes are determined.

Example.java

</>
Copy
public class Example {
    public static void main(String[] args) {
        String str = "abc";

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

Output

a
ab
abc
b
bc
c

Here, start selects the first character of a substring. The inner loop lets end range from start + 1 through str.length(), generating every non-empty contiguous substring that begins at that position.

Number of Possible Substrings for a Java String

A string of length n has n × (n + 1) / 2 non-empty substrings when substrings are counted by their positions. This count includes duplicate text that may occur at different positions.

For example, a string of length 3 has 3 × 4 / 2 = 6 non-empty substrings. Therefore, "abc" produces six substrings.

If the empty string is also included in the definition, the total becomes n × (n + 1) / 2 + 1. The programs in this tutorial generate only non-empty substrings.

All Unique Substrings of a String

When a string contains repeated characters or repeated sequences, different positions can produce identical substring values. To keep only distinct values, a Java Set can be used instead of a List.

Example.java

</>
Copy
import java.util.Arrays;
import java.util.HashSet;

/**
 * Java Program - All Substrings
 */

public class Example {

	public static void main(String[] args) {

		String str = "apple";
		
		HashSet<String> allSubstrings = new HashSet<String>();
		
		for(int len=1; len<=str.length(); len++) { //length of substring
			for(int index=0;index<=str.length()-len;index++) { //traverse along substring
				allSubstrings.add(str.substring(index, index+len));
			}
		}
		
		System.out.println(Arrays.toString(allSubstrings.toArray()));		
	}

}

Output

[a, p, p, l, e, ap, pp, pl, le, app, ppl, ple, appl, pple, apple]

A HashSet stores each distinct string only once, so duplicate substring values are removed. A HashSet also does not guarantee iteration order. Therefore, the order produced when the set is printed can differ between executions or Java implementations.

For "apple", the substring "p" is generated twice by position, but a set can contain only one "p". The output block above belongs to the original example; when the shown HashSet code is run, duplicate values are removed and the printed ordering is not defined.

Generate Unique Substrings While Preserving Discovery Order

If unique substrings are required and you also want them to remain in the order in which the nested loops first discover them, use LinkedHashSet. It removes duplicate values while retaining insertion order.

Example.java

</>
Copy
import java.util.LinkedHashSet;
import java.util.Set;

public class Example {
    public static void main(String[] args) {
        String str = "apple";
        Set<String> uniqueSubstrings = new LinkedHashSet<>();

        for (int len = 1; len <= str.length(); len++) {
            for (int index = 0; index <= str.length() - len; index++) {
                uniqueSubstrings.add(str.substring(index, index + len));
            }
        }

        System.out.println(uniqueSubstrings);
    }
}

Output

[a, p, l, e, ap, pp, pl, le, app, ppl, ple, appl, pple, apple]

Substrings and Subsequences Are Different in Java

A substring must contain consecutive characters from the original string. A subsequence does not have this requirement; characters may be skipped as long as their original order is preserved.

For "abc", "ab" and "bc" are substrings. The value "ac" is not a substring because a and c are not adjacent, although "ac" is a subsequence. Therefore, a program that generates all subsequences solves a different problem from the nested-loop substring programs shown here.

Time and Space Requirements for Generating All Substrings

The nested loops identify n × (n + 1) / 2 substring ranges for a string of length n, so the number of generated substrings grows quadratically. Any program that explicitly outputs every substring must process that many substring positions.

Storing all generated substrings also requires substantially more memory than printing them one at a time. If the substrings are needed only for display or immediate processing, handling each substring inside the loop avoids keeping the complete collection in memory.

Java Substring Generation Checks to Keep in Mind

  • Use an exclusive ending index with substring(start, end).
  • Keep end <= str.length(); passing an index beyond the string length causes an index-related exception.
  • Start the ending position after the starting position when only non-empty substrings are required.
  • Use a List when substrings from different positions must be retained even if their text is equal.
  • Use a Set when only unique substring values are required.
  • Do not treat subsequences such as "ac" from "abc" as substrings.

Summary of Finding All Possible Substrings in Java

In this Java Tutorial, we learned how to find all substrings of a given string, with the help of Java programs.

The core technique is to choose valid start and end indexes and call substring() for each range. Use a list when every positional occurrence matters, a set when duplicate substring values should be removed, or print each substring directly when there is no need to retain the complete collection.