Given string str the task is to expand the string as follows:
If the string is abcd, the resultant string will be d, cd, bcd, and abcd in the concatenated form i.e. dcdbcdabcd. We basically need to concatenate all suffixes.
Examples:
Input: str = “neveropen”
Output: sksekseeksneveropenInput str = “water”
Output rerteraterwater
Simple Approach:
- Iterate through the string in reverse order i.e. from the last index to the first.
- Print the sub-strings from the current index position till the end of the string.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print the expansion of the stringvoid printExpansion(string str){ int size = 0; for (int i = str.length() - 1; i >= 0; i--) { // Take sub-string from i to n-1 string subStr = str.substr(i, ++size); // Print the sub-string cout << subStr; }}// Driver codeint main(){ string str = "neveropen"; printExpansion(str); return 0;} |
Java
// Java implementation of the approach public class GFG { // Function to print the expansion of the string static void printExpansion(String str) { for (int i = str.length() - 1; i >= 0; i--) { // Take sub-string from i to n-1 String subStr = str.substring(i); // Print the sub-string System.out.print(subStr); } } // Driver code public static void main(String args[]) { String str = "neveropen"; printExpansion(str); } // This code is contributed by Ryuga} |
Python3
# Python3 implementation of the approach# Function to print the expansion of the stringdef printExpansion(str): for i in range(len(str)-1, -1, -1): # Take sub-string from i to n-1 for j in range(i, len(str)): print(str[j], end ="")# Driver codestr = "neveropen"printExpansion(str) |
C#
// C# implementation of the approach using System;class GFG { // Function to print the expansion of the string static void printExpansion(String str) { for (int i = (int)str.Length - 1; i >= 0; i--) { // Take sub-string from i to n-1 String subStr = str.Substring(i); // Print the sub-string Console.Write(subStr); } } // Driver code static public void Main(String []args) { String str = "neveropen"; printExpansion(str); } } // This code is contributed by Arnab Kundu |
Javascript
<script>// Javascript implementation of the approach// Function to print the expansion of the stringfunction printExpansion(str){ var size = 0; for (var i = str.length - 1; i >= 0; i--) { // Take sub-string from i to n-1 var subStr = str.substring(i, i + ++size); // Print the sub-string document.write( subStr); }}// Driver codevar str = "neveropen";printExpansion(str);</script> |
Output
sksekseeksneveropen
Complexity Analysis:
- Time Complexity: O(n2)
- Auxiliary Space: O(n)
Efficient Approach:
Maintain a suffix string (which is initially empty). Keep traversing from the end and keep appending the current character.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to print the expansion of the stringvoid printExpansion(string str){ string suff = ""; for (int i = str.length() - 1; i >= 0; i--) { // Take sub-string from i to n-1 suff = suff + str[i]; // Print the sub-string cout << suff; }}// Driver codeint main(){ string str = "neveropen"; printExpansion(str); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class solution{// Function to print the expansion of the stringstatic void printExpansion(String str){ String suff = ""; for (int i = str.length() - 1; i >= 0; i--) { // Take sub-string from i to n-1 suff = suff + str.charAt(i); // Print the sub-string System.out.print(suff); }}// Driver codepublic static void main(String args[]){ String str = "neveropen"; printExpansion(str);}} |
Python3
# Python3 implementation of the approach# Function to print the expansion # of the stringdef printExpansion( str): suff = "" for i in range (len (str) - 1, -1, -1) : # Take sub-string from i to n-1 suff = suff + str[i] # Print the sub-string print (suff, end = "")# Driver codeif __name__ == "__main__": str = "neveropen" printExpansion(str)# This code is contributed by ita_c |
C#
// C# Implementation of the above approachusing System; class GFG{// Function to print // the expansion of the stringstatic void printExpansion(String str){ String suff = ""; for (int i = str.Length - 1; i >= 0; i--) { // Take sub-string from i to n-1 suff = suff + str[i]; // Print the sub-string Console.Write(suff); }}// Driver codepublic static void Main(String []args){ String str = "neveropen"; printExpansion(str);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation of the approach// Function to print the expansion of the stringfunction printExpansion(str){ var suff = ""; for (var i = str.length - 1; i >= 0; i--) { // Take sub-string from i to n-1 suff = suff + str[i]; // Print the sub-string document.write( suff); }}// Driver codevar str = "neveropen";printExpansion(str);// This code is contributed by rrrtnx.</script> |
Output
sskskeskeeskeeg
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
Recursive Approach:
Steps:
- If the length of the string str is 0, return an empty string.
- Otherwise, recursively call the function expand_string with the substring str[1:] and append the substring str itself to the result of the recursive call.
- Finally, return the concatenated result.
Below is the implementation of the above approach:
C++
#include <iostream>#include <string>// Function to expand a string using recursionstd::string ExpandString(const std::string& str){ // Base case if (str.length() == 0) { return ""; } else { // Recursive case return ExpandString(str.substr(1)) + str; }}int main(){ std::string input_str = "neveropen"; std::string expanded_str = ExpandString(input_str); std::cout << expanded_str << std::endl; return 0;} |
Java
public class Main { // Function to expand a string using recursion public static String expandString(String str) { // Base case if (str.length() == 0) { return ""; } else { // Recursive case return expandString(str.substring(1)) + str; } } public static void main(String[] args) { String inputStr = "neveropen"; String expandedStr = expandString(inputStr); System.out.println(expandedStr); }}// This code is contributed by shivamgupta0987654321 |
Python
# Python implementation of the approachdef expand_string(str): # Base case if len(str) == 0: return "" else: # Recursive case return expand_string(str[1:]) + str# Driver Codeinput_str = "neveropen"expanded_str = expand_string(input_str)print(expanded_str) |
C#
using System;class Program{ // Function to expand a string using recursion static string ExpandString(string str) { // Base case if (str.Length == 0) { return ""; } else { // Recursive case return ExpandString(str.Substring(1)) + str; } } static void Main() { string inputStr = "neveropen"; string expandedStr = ExpandString(inputStr); Console.WriteLine(expandedStr); }} |
Javascript
function GFG(str) { if (str.length === 0) { return ""; } else { // Recursive case: call the function with the substring starting from // the second character and concatenate the original string at the end return GFG(str.substring(1)) + str; }}const inputStr = "neveropen";const expandedStr = GFG(inputStr);console.log(expandedStr); |
Output
sksekseeksneveropen
Time Complexity: O(n^2), where n is the length of the input string str.
Auxiliary Space: O(n^2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
