Concatenate suffixes of a String

0 0 5 minutes read

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 = “zambiatek”
Output: sksekseekszambiatek

Input 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 string
void 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 code
int main()
{
    string str = "zambiatek";
    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 = "zambiatek"; 
        printExpansion(str); 
     
    } 
    // This code is contributed by Ryuga
}

Python3

# Python3 implementation of the approach
 
# Function to print the expansion of the string
def 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 code
str = "zambiatek"
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 = "zambiatek"; 
        printExpansion(str); 
      
    } 
}
    // This code is contributed by Arnab Kundu

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to print the expansion of the string
function 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 code
var str = "zambiatek";
printExpansion(str);
 
</script>

Output

sksekseekszambiatek

Complexity Analysis:

Time Complexity: O(n²)
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 string
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
        cout << suff;
    }
}
 
// Driver code
int main()
{
    string str = "zambiatek";
    printExpansion(str);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class solution
{
 
// Function to print the expansion of the string
static 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 code
public static void main(String args[])
{
    String str = "zambiatek";
    printExpansion(str);
 
}
}

Python3

# Python3 implementation of the approach
 
# Function to print the expansion 
# of the string
def 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 code
if __name__ == "__main__":
 
    str = "zambiatek"
    printExpansion(str)
 
# This code is contributed by ita_c

C#

// C# Implementation of the above approach
using System;
     
class GFG
{
 
// Function to print 
// the expansion of the string
static 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 code
public static void Main(String []args)
{
    String str = "zambiatek";
    printExpansion(str);
}
}
 
// This code is contributed by PrinciRaj1992 

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to print the expansion of the string
function 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 code
var str = "zambiatek";
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 recursion
std::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 = "zambiatek";
    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 = "zambiatek";
        String expandedStr = expandString(inputStr);
        System.out.println(expandedStr);
    }
}
// This code is contributed by shivamgupta0987654321

Python

# Python implementation of the approach
def expand_string(str):
    # Base case
    if len(str) == 0:
        return ""
    else:
        # Recursive case
        return expand_string(str[1:]) + str
 
 
# Driver Code
input_str = "zambiatek"
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 = "zambiatek";
        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 = "zambiatek";
const expandedStr = GFG(inputStr);
console.log(expandedStr);

Output

sksekseekszambiatek

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 zambiatek!