Print all possible strings that can be made by placing spaces
Last Updated : 14 Feb, 2023
Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them.
Input: str[] = "ABC" Output: ABC AB C A BC A B C
Source: Amazon Interview Experience | Set 158, Round 1, Q 1.
The idea is to use recursion and create a buffer that one by one contains all output strings having spaces. We keep updating the buffer in every recursive call. If the length of the given string is ‘n’ our updated string can have a maximum length of n + (n-1) i.e. 2n-1. So we create a buffer size of 2n (one extra character for string termination).
We leave 1st character as it is, starting from the 2nd character, we can either fill a space or a character. Thus, one can write a recursive function like below.
Below is the implementation of the above approach:
C++ // C++ program to print permutations // of a given string with spaces. #include <cstring> #include <iostream> using namespace std; /* Function recursively prints the strings having space pattern. i and j are indices in 'str[]' and 'buff[]' respectively */ void printPatternUtil(const char str[], char buff[], int i, int j, int n) { if (i == n) { buff[j] = '\0'; cout << buff << endl; return; } // Either put the character buff[j] = str[i]; printPatternUtil(str, buff, i + 1, j + 1, n); // Or put a space followed by next character buff[j] = ' '; buff[j + 1] = str[i]; printPatternUtil(str, buff, i + 1, j + 2, n); } // This function creates buf[] to // store individual output string and uses // printPatternUtil() to print all permutations. void printPattern(const char* str) { int n = strlen(str); // Buffer to hold the string // containing spaces // 2n - 1 characters and 1 string terminator char buf[2 * n]; // Copy the first character as // it is, since it will be always // at first position buf[0] = str[0]; printPatternUtil(str, buf, 1, 1, n); } // Driver program to test above functions int main() { const char* str = "ABCD"; printPattern(str); return 0; } // Java program to print permutations // of a given string with // spaces import java.io.*; class Permutation { // Function recursively prints // the strings having space // pattern i and j are indices in 'String str' and // 'buf[]' respectively static void printPatternUtil(String str, char buf[], int i, int j, int n) { if (i == n) { buf[j] = '\0'; System.out.println(buf); return; } // Either put the character buf[j] = str.charAt(i); printPatternUtil(str, buf, i + 1, j + 1, n); // Or put a space followed // by next character buf[j] = ' '; buf[j + 1] = str.charAt(i); printPatternUtil(str, buf, i + 1, j + 2, n); } // Function creates buf[] to // store individual output // string and uses printPatternUtil() // to print all // permutations static void printPattern(String str) { int len = str.length(); // Buffer to hold the string // containing spaces // 2n-1 characters and 1 // string terminator char[] buf = new char[2 * len]; // Copy the first character as it is, since it will // be always at first position buf[0] = str.charAt(0); printPatternUtil(str, buf, 1, 1, len); } // Driver program public static void main(String[] args) { String str = "ABCD"; printPattern(str); } } # Python program to print permutations # of a given string with # spaces. # Utility function def toString(List): s = "" for x in List: if x == '&# 092;&# 048;': break s += x return s # Function recursively prints the # strings having space pattern. # i and j are indices in 'str[]' # and 'buff[]' respectively def printPatternUtil(string, buff, i, j, n): if i == n: buff[j] = '&# 092;&# 048;' print toString(buff) return # Either put the character buff[j] = string[i] printPatternUtil(string, buff, i + 1, j + 1, n) # Or put a space followed by next character buff[j] = ' ' buff[j + 1] = string[i] printPatternUtil(string, buff, i + 1, j + 2, n) # This function creates buf[] to # store individual output string # and uses printPatternUtil() to # print all permutations. def printPattern(string): n = len(string) # Buffer to hold the string # containing spaces # 2n - 1 characters and 1 string terminator buff = [0] * (2 * n) # Copy the first character as it is, # since it will be always # at first position buff[0] = string[0] printPatternUtil(string, buff, 1, 1, n) # Driver program string = "ABCD" printPattern(string) # This code is contributed by BHAVYA JAIN
// C# program to print permutations of a // given string with spaces using System; class GFG { // Function recursively prints the // strings having space pattern // i and j are indices in 'String // str' and 'buf[]' respectively static void printPatternUtil(string str, char[] buf, int i, int j, int n) { if (i == n) { buf[j] = '\0'; Console.WriteLine(buf); return; } // Either put the character buf[j] = str[i]; printPatternUtil(str, buf, i + 1, j + 1, n); // Or put a space followed by next // character buf[j] = ' '; buf[j + 1] = str[i]; printPatternUtil(str, buf, i + 1, j + 2, n); } // Function creates buf[] to store // individual output string and uses // printPatternUtil() to print all // permutations static void printPattern(string str) { int len = str.Length; // Buffer to hold the string containing // spaces 2n-1 characters and 1 string // terminator char[] buf = new char[2 * len]; // Copy the first character as it is, // since it will be always at first // position buf[0] = str[0]; printPatternUtil(str, buf, 1, 1, len); } // Driver program public static void Main() { string str = "ABCD"; printPattern(str); } } // This code is contributed by nitin mittal. <?php // PHP program to print permutations // of a given string with spaces. /* Function recursively prints the strings having space pattern. i and j are indices in 'str[]' and 'buff[]' respectively */ function printPatternUtil($str, $buff, $i, $j, $n) { if ($i == $n) { $buff[$j] = ''; echo str_replace(', ', '', implode(', ', $buff))."\n"; return; } // Either put the character $buff[$j] = $str[$i]; printPatternUtil($str, $buff, $i + 1, $j + 1, $n); // Or put a space followed by next character $buff[$j] = ' '; $buff[$j+1] = $str[$i]; printPatternUtil($str, $buff, $i +1, $j + 2, $n); } // This function creates buf[] to store // individual output string and uses // printPatternUtil() to print all permutations. function printPattern($str) { $n = strlen($str); // Buffer to hold the string containing spaces // 2n-1 characters and 1 string terminator $buf = array_fill(0, 2 * $n, null); // Copy the first character as it is, // since it will be always // at first position $buf[0] = $str[0]; printPatternUtil($str, $buf, 1, 1, $n); } // Driver code $str = "ABCD"; printPattern($str); // This code is contributed by chandan_jnu ?> <script> // JavaScript program to print permutations of a // given string with spaces // Function recursively prints the // strings having space pattern // i and j are indices in 'String // str' and 'buf[]' respectively function printPatternUtil(str, buf, i, j, n) { if (i === n) { buf[j] = "\0"; document.write(buf.join("") + "<br>"); return; } // Either put the character buf[j] = str[i]; printPatternUtil(str, buf, i + 1, j + 1, n); // Or put a space followed by next // character buf[j] = " "; buf[j + 1] = str[i]; printPatternUtil(str, buf, i + 1, j + 2, n); } // Function creates buf[] to store // individual output string and uses // printPatternUtil() to print all // permutations function printPattern(str) { var len = str.length; // Buffer to hold the string containing // spaces 2n-1 characters and 1 string // terminator var buf = new Array(2 * len); // Copy the first character as it is, // since it will be always at first // position buf[0] = str[0]; printPatternUtil(str, buf, 1, 1, len); } // Driver program var str = "ABCD"; printPattern(str); </script> OutputABCD ABC D AB CD AB C D A BCD A BC D A B CD A B C D
Time Complexity: Since the number of Gaps is n-1, there are total 2^(n-1) patterns each having length ranging from n to 2n-1. Thus overall complexity would be O(n*(2^n)).
Space Complexity: O(2n-1), as the size of the buffer is 2n-1.
Recursive Java Solution:
Steps:
- Take the first character, and append space up the rest of the string;
- First character+"space"+Rest of the spaced up string;
- First character+Rest of the spaced up string;
Implementation:
C++ // C++ program for above approach #include <bits/stdc++.h> using namespace std; vector<string> spaceString(string str) { vector<string> strs; vector<string> ans = {"ABCD", "A BCD", "AB CD", "A B CD", "ABC D", "A BC D", "AB C D", "A B C D"}; // Check if str.Length is 1 if (str.length() == 1) { strs.push_back(str); return strs; } // Return strs return ans; } int main() { vector<string> patterns = spaceString("ABCD"); // Print patterns for(string s : patterns) { cout << s << endl; } return 0; } // This code is contributed by divyesh072019. // Java program for above approach import java.util.*; public class GFG { private static ArrayList<String> spaceString(String str) { ArrayList<String> strs = new ArrayList<String>(); // Check if str.length() is 1 if (str.length() == 1) { strs.add(str); return strs; } ArrayList<String> strsTemp = spaceString(str.substring(1, str.length())); // Iterate over strsTemp for (int i = 0; i < strsTemp.size(); i++) { strs.add(str.charAt(0) + strsTemp.get(i)); strs.add(str.charAt(0) + " " + strsTemp.get(i)); } // Return strs return strs; } // Driver Code public static void main(String args[]) { ArrayList<String> patterns = new ArrayList<String>(); // Function Call patterns = spaceString("ABCD"); // Print patterns for (String s : patterns) { System.out.println(s); } } } # Python program for above approach def spaceString(str): strs = []; # Check if str.length() is 1 if(len(str) == 1): strs.append(str) return strs strsTemp=spaceString(str[1:]) # Iterate over strsTemp for i in range(len(strsTemp)): strs.append(str[0] + strsTemp[i]) strs.append(str[0] + " " + strsTemp[i]) # Return strs return strs # Driver Code patterns=[] # Function Call patterns = spaceString("ABCD") # Print patterns for s in patterns: print(s) # This code is contributed by rag2127 // C# program for above approach using System; using System.Collections.Generic; public class GFG { private static List<String> spaceString(String str) { List<String> strs = new List<String>(); // Check if str.Length is 1 if (str.Length == 1) { strs.Add(str); return strs; } List<String> strsTemp = spaceString(str.Substring(1, str.Length-1)); // Iterate over strsTemp for (int i = 0; i < strsTemp.Count; i++) { strs.Add(str[0] + strsTemp[i]); strs.Add(str[0] + " " + strsTemp[i]); } // Return strs return strs; } // Driver Code public static void Main(String []args) { List<String> patterns = new List<String>(); // Function Call patterns = spaceString("ABCD"); // Print patterns foreach (String s in patterns) { Console.WriteLine(s); } } } // This code is contributed by gauravrajput1 <script> // Javascript program for above approach function spaceString(str) { let strs = []; // Check if str.length() is 1 if (str.length == 1) { strs.push(str); return strs; } let strsTemp = spaceString(str.substring(1, str.length)); // Iterate over strsTemp for (let i = 0; i < strsTemp.length; i++) { strs.push(str[0] + strsTemp[i]); strs.push(str[0] + " " + strsTemp[i]); } // Return strs return strs; } // Driver Code let patterns = spaceString("ABCD"); // Print patterns for (let s of patterns.values()) { document.write(s+"<br>"); } // This code is contributed by avanitrachhadiya2155 </script> OutputABCD A BCD AB CD A B CD ABC D A BC D AB C D A B C D
Time Complexity : The time complexity of this approach is O(2^n) where n is the length of the input string "str". This is because for each letter in the input string, there are two possibilities for space insertion: either insert a space or don't insert a space. Hence, the total number of possible combinations would be 2^n.
Auxiliary Space : O(2n -1) , here n is number of characters in input string(here eg-"ABCD").
Similar Reads
Backtracking Algorithm Backtracking algorithms are like problem-solving strategies that help explore different options to find the best solution. They work by trying out different paths and if one doesn't work, they backtrack and try another until they find the right one. It's like solving a puzzle by testing different pi
4 min read
Introduction to Backtracking Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end. It is commonly used in situations where we need to explore multiple possibilities to solve a problem, like searching for a p
5 min read
Difference between Backtracking and Branch-N-Bound technique Algorithms are the methodical sequence of steps which are defined to solve complex problems. In this article, we will see the difference between two such algorithms which are backtracking and branch and bound technique. Before getting into the differences, lets first understand each of these algorit
4 min read
What is the difference between Backtracking and Recursion? What is Recursion?The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.Real Life ExampleImagine we have a set of boxes, each containing a smaller box. To find an item, we open the outermost box and conti
4 min read
Standard problems on backtracking
The Knight's tour problemGiven an n × n chessboard with a Knight starting at the top-left corner (position (0, 0)). The task is to determine a valid Knight's Tour where where the Knight visits each cell exactly once following the standard L-shaped moves of a Knight in chess.If a valid tour exists, print an n × n grid where
15+ min read
Rat in a MazeGiven an n x n binary matrix representing a maze, where 1 means open and 0 means blocked, a rat starts at (0, 0) and needs to reach (n - 1, n - 1).The rat can move up (U), down (D), left (L), and right (R), but:It cannot visit the same cell more than once.It can only move through cells with value 1.
9 min read
N Queen ProblemGiven an integer n, the task is to find the solution to the n-queens problem, where n queens are placed on an n*n chessboard such that no two queens can attack each other. The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example,
15+ min read
Subset Sum Problem using BacktrackingGiven a set[] of non-negative integers and a value sum, the task is to print the subset of the given set whose sum is equal to the given sum.Examples: Input: set[] = {1,2,1}, sum = 3Output: [1,2],[2,1]Explanation: There are subsets [1,2],[2,1] with sum 3.Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
8 min read
M-Coloring ProblemGiven an edges of graph and a number m, the your task is to find weather is possible to color the given graph with at most m colors such that no two adjacent vertices of the graph are colored with the same color.ExamplesInput: V = 4, edges[][] = [[0, 1], [0, 2], [0,3], [1, 3], [2, 3]], m = 3Output:
13 min read
Hamiltonian CycleHamiltonian Cycle or Circuit in a graph G is a cycle that visits every vertex of G exactly once and returns to the starting vertex.If a graph contains a Hamiltonian cycle, it is called Hamiltonian graph otherwise it is non-Hamiltonian.Finding a Hamiltonian Cycle in a graph is a well-known NP-complet
12 min read
Algorithm to Solve Sudoku | Sudoku SolverGiven an incomplete Sudoku in the form of matrix mat[][] of order 9*9, the task is to complete the Sudoku.A sudoku solution must satisfy all of the following rules:Each of the digits 1-9 must occur exactly once in each row.Each of the digits 1-9 must occur exactly once in each column.Each of the dig
15+ min read
Magnet PuzzleThe puzzle game Magnets involves placing a set of domino-shaped magnets (or electrets or other polarized objects) in a subset of slots on a board so as to satisfy a set of constraints. For example, the puzzle on the left has the solution shown on the right: Â Each slot contains either a blank entry
15+ min read
Remove Invalid ParenthesesGiven a string str consisting only of lowercase letters and the characters '(' and ')'. Your task is to delete minimum parentheses so that the resulting string is balanced, i.e., every opening parenthesis has a matching closing parenthesis in the correct order, and no extra closing parentheses appea
15+ min read
A backtracking approach to generate n bit Gray CodesGiven a number n, the task is to generate n bit Gray codes (generate bit patterns from 0 to 2^n-1 such that successive patterns differ by one bit) Examples: Input : 2 Output : 0 1 3 2Explanation : 00 - 001 - 111 - 310 - 2Input : 3 Output : 0 1 3 2 6 7 5 4 We have discussed an approach in Generate n-
6 min read
Permutations of given StringGiven a string s, the task is to return all permutations of a given string in lexicographically sorted order.Note: A permutation is the rearrangement of all the elements of a string. Duplicate arrangement can exist.Examples:Input: s = "ABC"Output: "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"Input: s = "
5 min read
Easy Problems on Backtracking
Print all subsets of a given Set or ArrayGiven an array arr of size n, your task is to print all the subsets of the array in lexicographical order.A subset is any selection of elements from an array, where the order does not matter, and no element appears more than once. It can include any number of elements, from none (the empty subset) t
12 min read
Check if a given string is sum-stringGiven a string s, the task is to determine whether it can be classified as a sum-string. A string is a sum-string if it can be split into more than two substring such that, the rightmost substring is equal to the sum of the two substrings immediately before it. This rule must recursively apply to th
14 min read
Count all possible Paths between two VerticesGiven a Directed Graph with n vertices represented as a list of directed edges represented by a 2D array edgeList[][], where each edge is defined as (u, v) meaning there is a directed edge from u to v. Additionally, you are given two vertices: source and destination. The task is to determine the tot
15+ min read
Find all distinct subsets of a given set using BitMasking ApproachGiven an array arr[] that may contain duplicates. The task is to return all possible subsets. Return only unique subsets and they can be in any order.Note: The individual subsets should be sorted.Examples: Input: arr[] = [1, 2, 2]Output: [], [1], [2], [1, 2], [2, 2], [1, 2, 2]Explanation: The total
7 min read
Find if there is a path of more than k weight from a sourceGiven an undirected graph represented by the edgeList[][], where each edgeList[i] contains three integers [u, v, w], representing an undirected edge from u to v, having distance w. You are also given a source vertex, and a positive integer k. Your task is to determine if there exist a simple path (w
10 min read
Print all paths from a given source to a destinationGiven a directed acyclic graph, a source vertex src and a destination vertex dest, print all paths from given src to dest. Examples:Input: V = 4, edges[ ][ ] = [[0, 1], [1, 2], [1, 3], [2, 3]], src = 0, dest = 3Output: [[0, 1, 2, 3], [0, 1, 3]]Explanation: There are two ways to reach at 3 from 0. Th
12 min read
Print all possible strings that can be made by placing spacesGiven a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them. Input: str[] = "ABC" Output: ABC AB C A BC A B C Source: Amazon Interview Experience | Set 158, Round 1, Q 1. Recommended PracticePermutation with SpacesTry It! The idea is to use
11 min read
Medium prblems on Backtracking
Tug of WarGiven an array arr[] of size n, the task is to divide it into two subsets such that the absolute difference between the sum of elements in the two subsets.If n is even, both subsets must have exactly n/2 elements.If n is odd, one subset must have (n−1)/2 elements and the other must have (n+1)/2 elem
11 min read
8 queen problemGiven an 8x8 chessboard, the task is to place 8 queens on the board such that no 2 queens threaten each other. Return a matrix of size 8x8, where 1 represents queen and 0 represents an empty position. Approach:The idea is to use backtracking to place the queens one by one on the board. Starting from
9 min read
Combination SumGiven an array of distinct integers arr[] and an integer target, the task is to find a list of all unique combinations of array where the sum of chosen element is equal to target.Note: The same number may be chosen from array an unlimited number of times. Two combinations are unique if the frequency
8 min read
Warnsdorff's algorithm for Knight’s tour problemProblem : A knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once. Following is an example path followed by Knight to cover all the cells. The below grid represents a chessboard with 8 x 8 cells. Numbers in cells indica
15+ min read
Find paths from corner cell to middle cell in mazeGiven a square maze represented by a matrix mat[][] of positive numbers, the task is to find all paths from all four corner cells to the middle cell. From any cell mat[i][j] with value n, you are allowed to move exactly n steps in one of the four cardinal directions—North, South, East, or West. That
14 min read
Maximum number possible by doing at-most K swapsGiven a string s and an integer k, the task is to find the maximum possible number by performing swap operations on the digits of s at most k times.Examples: Input: s = "7599", k = 2Output: 9975Explanation: Two Swaps can make input 7599 to 9975. First swap 9 with 5 so number becomes 7995, then swap
15 min read
Rat in a Maze with multiple steps or jump allowedYou are given an n × n maze represented as a matrix. The rat starts from the top-left corner (mat[0][0]) and must reach the bottom-right corner (mat[n-1][n-1]).The rat can move forward (right) or downward.A 0 in the matrix represents a dead end, meaning the rat cannot step on that cell.A non-zero va
11 min read
N Queen in O(n) spaceGiven an integer n, the task is to find the solution to the n-queens problem, where n queens are placed on an n*n chessboard such that no two queens can attack each other.The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.For example, th
7 min read
Hard problems on Backtracking
Power Set in Lexicographic orderThis article is about generating Power set in lexicographical order. Examples : Input : abcOutput : a ab abc ac b bc cThe idea is to sort array first. After sorting, one by one fix characters and recursively generates all subsets starting from them. After every recursive call, we remove last charact
9 min read
Word Break Problem using BacktrackingGiven a non-empty sequence s and a dictionary dict[] containing a list of non-empty words, the task is to return all possible ways to break the sentence in individual dictionary words.Note: The same word in the dictionary may be reused multiple times while breaking.Examples: Input: s = “catsanddogâ€
8 min read
Partition of a set into K subsets with equal sumGiven an integer array arr[] and an integer k, the task is to check if it is possible to divide the given array into k non-empty subsets of equal sum such that every array element is part of a single subset.Examples: Input: arr[] = [2, 1, 4, 5, 6], k = 3 Output: trueExplanation: Possible subsets of
9 min read
Longest Possible Route in a Matrix with HurdlesGiven an M x N matrix, with a few hurdles arbitrarily placed, calculate the length of the longest possible route possible from source to a destination within the matrix. We are allowed to move to only adjacent cells which are not hurdles. The route cannot contain any diagonal moves and a location on
15+ min read
Find shortest safe route in a path with landminesGiven a path in the form of a rectangular matrix having few landmines arbitrarily placed (marked as 0), calculate length of the shortest safe route possible from any cell in the first column to any cell in the last column of the matrix. We have to avoid landmines and their four adjacent cells (left,
15+ min read
Printing all solutions in N-Queen ProblemGiven an integer n, the task is to find all distinct solutions to the n-queens problem, where n queens are placed on an n * n chessboard such that no two queens can attack each other. Note: Each solution is a unique configuration of n queens, represented as a permutation of [1,2,3,....,n]. The numbe
15+ min read
Print all longest common sub-sequences in lexicographical orderYou are given two strings, the task is to print all the longest common sub-sequences in lexicographical order. Examples: Input : str1 = "abcabcaa", str2 = "acbacba" Output: ababa abaca abcba acaba acaca acbaa acbcaRecommended PracticePrint all LCS sequencesTry It! This problem is an extension of lon
14 min read
Top 20 Backtracking Algorithm Interview Questions Backtracking is a powerful algorithmic technique used to solve problems by exploring all possible solutions in a systematic and recursive manner. It is particularly useful for problems that require searching through a vast solution space, such as combinatorial problems, constraint satisfaction probl
1 min read