All substrings of a given String

Last Updated : 14 Feb, 2025

Given a string s, containing lowercase alphabetical characters. The task is to print all non-empty substrings of the given string.

Examples :

Input : s = "abc"
Output : "a", "ab", "abc", "b", "bc", "c"
Input : s = "ab"
Output : "a", "ab", "b"
Input : s = "a"
Output : "a"

[Expected Approach] - Using Iteration

The idea is to use two nested loops.
The outer loop picks the starting index (loop for i from 0 to n-1)
The inner loop picks the ending ending index (loop for j to n-1)

C++

// C++ program to find all the // substrings of given string #include <bits/stdc++.h> using namespace std; // Function to find all substrings vector<string> findSubstrings(string &s) {  // to store all substrings  vector<string> res;  for(int i = 0; i < s.length(); i++) {  for(int j = i; j < s.length(); j++) {    // substr function takes starting index  // and length as parameters  res.push_back(s.substr(i, j-i+1));  }  }  return res; } int main() {  string s = "abc";  vector<string> res = findSubstrings(s);  for(auto i:res) {  cout<< i <<" ";  }  return 0; }

#include <stdio.h> #include <string.h> // Function to find all substrings void findSubstrings(char *s) {    // to store all substrings  int len = strlen(s);  for (int i = 0; i < len; i++) {  for (int j = i; j < len; j++) {  for (int k = i; k <= j; k++) {  putchar(s[k]);  }  printf(" ");  }  } } int main() {  char s[] = "abc";  findSubstrings(s);  return 0; }

Java

// Function to find all substrings import java.util.ArrayList; import java.util.List; public class Main {  public static List<String> findSubstrings(String s) {    // to store all substrings  List<String> res = new ArrayList<>();  for (int i = 0; i < s.length(); i++) {  for (int j = i; j < s.length(); j++) {    // substr function takes starting index  // and ending index + 1 as parameters  res.add(s.substring(i, j + 1));  }  }  return res;  }  public static void main(String[] args) {  String s = "abc";  List<String> res = findSubstrings(s);  for (String i : res) {  System.out.print(i + " ");  }  } }

Python

# Function to find all substrings def find_substrings(s): # to store all substrings res = [] for i in range(len(s)): for j in range(i, len(s)): res.append(s[i:j+1]) return res s = 'abc' res = find_substrings(s) for i in res: print(i, end=' ')

// Function to find all substrings using System; using System.Collections.Generic; class Program {  public static List<string> FindSubstrings(string s) {    List<string> res = new List<string>();    for (int i = 0; i < s.Length; i++) {  for (int j = i; j < s.Length; j++) {    // substr function takes starting index  // and length as parameters  res.Add(s.Substring(i, j - i + 1));  }  }  return res;  }  static void Main() {  string s = "abc";  List<string> res = FindSubstrings(s);  foreach (var i in res) {  Console.Write(i + " ");  }  } }

JavaScript

// Function to find all substrings function findSubstrings(s) {    // to store all substrings  let res = [];  for (let i = 0; i < s.length; i++) {  for (let j = i; j < s.length; j++) {    // substr function takes starting index  // and ending index + 1 as parameters  res.push(s.substring(i, j + 1));  }  }  return res; } let s = 'abc'; let res = findSubstrings(s); res.forEach(i => {  process.stdout.write(i + ' '); });

Output

a ab abc b bc c

[Interesting Approach] - Using Recursion

The idea is to recursively generate all possible substrings of the given string s. To do so, create an array of string res[] to store the substrings of string s and an empty string cur to store the current string. Start from the 0th index and for each index ind, add the current character s[ind] in the string cur, and add the string cur in res[]. Then, move to index ind + 1, and recursively generate the all substrings. At each recursive call, check if string cur is empty, if so, skip the current character to start the string from next index ind + 1. At last print all the substrings.

C++

// C++ program to find all the // substrings of given string #include <bits/stdc++.h> using namespace std; // Recursive Function to find all // substrings of a string void subString(string &s, int n, int index,   string &cur, vector<string> &res) {  // if we have reached the   // end of the string  if (index == n) {  return;  }  // add the character s[index]   // to the current string  cur.push_back(s[index]);  // add the current string in result  res.push_back(cur);  // move to next index  subString(s, n, index + 1, cur, res);  // remove the current character  // from the current string   cur.pop_back();    // if current string is empty  // skip the current index to  // start the new substring  if(cur.empty()) {  subString(s, n, index + 1, cur, res);  } } // Function to find all substrings vector<string> findSubstrings(string s) {  // to store all substrings  vector<string> res;    // to store current string  string cur = "";  subString(s, s.length(), 0, cur, res);  return res; } int main() {  string s = "abc";  vector<string> res = findSubstrings(s);  for(auto i:res) {  cout<< i <<" ";  }  return 0; }

Java

// Java program to find all the // substrings of given string import java.util.*; class GFG {  // Recursive Function to find all  // substrings of a string  static void subString(String s, int n, int index,  StringBuilder cur, List<String> res) {  // if we have reached the  // end of the string  if (index == n) {  return;  }  // add the character s.charAt(index)  // to the current string  cur.append(s.charAt(index));  // add the current string in result  res.add(cur.toString());  // move to next index  subString(s, n, index + 1, cur, res);  // remove the current character  // from the current string  cur.deleteCharAt(cur.length() - 1);  // if current string is empty  // skip the current index to  // start the new substring  if (cur.length() == 0) {  subString(s, n, index + 1, cur, res);  }  }  // Function to find all substrings  static List<String> findSubstrings(String s) {  // to store all substrings  List<String> res = new ArrayList<>();  // to store current string  StringBuilder cur = new StringBuilder();  subString(s, s.length(), 0, cur, res);  return res;  }  public static void main(String[] args) {  String s = "abc";  List<String> res = findSubstrings(s);  for (String str : res) {  System.out.print(str + " ");  }  } }

Python

# Python program to find all the # substrings of given string # Recursive Function to find all # substrings of a string def subString(s, n, index, cur, res): # if we have reached the # end of the string if index == n: return # add the character s[index] # to the current string cur += s[index] # add the current string in result res.append(cur) # move to next index subString(s, n, index + 1, cur, res) # remove the current character # from the current string cur = cur[:-1] # if current string is empty # skip the current index to # start the new substring if not cur: subString(s, n, index + 1, cur, res) # Function to find all substrings def findSubstrings(s): # to store all substrings res = [] # to store current string cur = "" subString(s, len(s), 0, cur, res) return res if __name__ == "__main__": s = "abc" res = findSubstrings(s) print(" ".join(res))

// C# program to find all the // substrings of given string using System; using System.Collections.Generic; class GFG {  // Recursive Function to find all  // substrings of a string  static void subString(string s, int n, int index,  List<char> cur, List<string> res) {  // if we have reached the  // end of the string  if (index == n) {  return;  }  // add the character s[index]  // to the current string  cur.Add(s[index]);  // add the current string in result  res.Add(new string(cur.ToArray()));  // move to next index  subString(s, n, index + 1, cur, res);  // remove the current character  // from the current string  cur.RemoveAt(cur.Count - 1);  // if current string is empty  // skip the current index to  // start the new substring  if (cur.Count == 0) {  subString(s, n, index + 1, cur, res);  }  }  // Function to find all substrings  static List<string> findSubstrings(string s) {  // to store all substrings  List<string> res = new List<string>();  // to store current string  List<char> cur = new List<char>();  subString(s, s.Length, 0, cur, res);  return res;  }  public static void Main() {  string s = "abc";  List<string> res = findSubstrings(s);  Console.WriteLine(string.Join(" ", res));  } }

JavaScript

// JavaScript program to find all the // substrings of given string // Recursive Function to find all // substrings of a string function subString(s, n, index, cur, res) {  // if we have reached the  // end of the string  if (index === n) {  return;  }  // add the character s[index]  // to the current string  cur += s[index];  // add the current string in result  res.push(cur);  // move to next index  subString(s, n, index + 1, cur, res);  // remove the current character  // from the current string  cur = cur.slice(0, -1);  // if current string is empty  // skip the current index to  // start the new substring  if (cur.length === 0) {  subString(s, n, index + 1, cur, res);  } } // Function to find all substrings function findSubstrings(s) {  // to store all substrings  let res = [];  // to store current string  let cur = "";  subString(s, s.length, 0, cur, res);  return res; } const s = "abc"; const res = findSubstrings(s); console.log(res.join(" "));