Problem

Given a string, write a program to return all possible substrings of that string. A substring is a contiguous sequence of characters within a string.

Examples

Example 1

1
2
3

Input: "abc"
Output: ["a", "ab", "abc", "b", "bc", "c"]
Explanation: The substrings of "abc" are generated by iterating through each starting position of the string and extending the substring until the end of the string.

Example 2

1
2
3

Input: "ab"
Output: ["a", "ab", "b"]
Explanation: From "ab", you take each starting position, extending from each starting point to generate "a", "ab", and "b".

Solution

Method 1 - Naive

  • To generate all substrings:
    • Start at every possible position in the string (known as the start index).
    • Extend the substring from the start position to every length that is valid, ending only when the end index reaches the end of the input string.
  • Use two nested loops: one for selecting the start position and one for calculating all substrings starting from the current position.

Approach

  1. Use nested loops:
    • The outer loop selects each character in the string as the starting point (start index).
    • The inner loop iterates through the possible lengths starting from the current character, generating substrings dynamically.
  2. Collect each substring into a list or directly print them.

In the Solution Class, these methods are encapsulated to compute substrings efficiently and maintain readability.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public List<String> generateSubstrings(String inputString) {
        List<String> substrings = new ArrayList<>();
        int n = inputString.length();

        for (int start = 0; start < n; start++) {               // Outer loop for starting position
            for (int end = start; end < n; end++) {             // Inner loop to form substrings
                substrings.add(inputString.substring(start, end + 1)); // Extract and add substring
            }
        }
        return substrings;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.generateSubstrings("abc"));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def generate_substrings(self, input_string: str):
        substrings = []
        n = len(input_string)
        for start in range(n):         # Outer loop for starting position
            for end in range(start, n): # Inner loop to form substrings
                substrings.append(input_string[start:end + 1]) # Append the substring
        return substrings

# Example usage:
solution = Solution()
print(solution.generate_substrings("abc"))

Complexity

  • ⏰ Time complexity: O(n^2). The outer loop runs n times (once for each character), and the inner loop runs up to n times for each outer loop iteration. This results in quadratic complexity.
  • 🧺 Space complexity: O(n^2). If storing all substrings into a list, the list can grow to a size proportional to the number of substrings.