mediumStringsPattern: Mixed
Reverse Substring Concatenation Solution
Problem Statement
Given a string `s` of length `n`, return a comma-separated string of all substrings of `s` in reverse order, where each substring in the output string should be in reverse order.
Examples
Example 1:
Input:abc
Output:c,b,a
Example 2:
Input:abcd
Output:d,c,b,a
Constraints
- 1 <= n <= 1000
- s contains only lowercase English letters
- s is not empty
- n is a positive integer
Time: O(n^3) Space: O(n^2)
An optimized approach would involve using a two-pointer technique to generate all substrings, reversing each substring as it is generated, and storing the reversed substrings in a data structure such as a list or array. The optimized approach has a time complexity of O(n^3) due to the nested loops and string reversal, and a space complexity of O(n^2) for storing the reversed substrings. By avoiding the overhead of string concatenation and using a more efficient data structure, the optimized approach achieves better performance.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def reverse_substring_concatenation(s):
n = len(s)
substrings = []
for i in range(n):
for j in range(i + 1, n + 1):
substring = s[i:j][::-1]
substrings.append(substring)
return ",".join(reversed(substrings))
for line in sys.stdin:
s = line.strip()
print(reverse_substring_concatenation(s))
break