Reverse Encode String — Problem Statement & Solution Guide
Problem Description
Given a string s, construct a new string by first reversing the order of all characters in s and then appending the original string s to the end of this reversed sequence. The resulting string is therefore the concatenation of the reversed input followed immediately by the original input. If the input is null or undefined, the function must return an empty string. The operation is deterministic and must be performed in linear time relative to the length of s.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Reverse Encode String"
WHY DOES IT MATTER?
Understanding how to manipulate strings efficiently is fundamental because many real‑world APIs, data pipelines, and encoding schemes rely on reversible transformations. Mastery of in‑place reversal and buffered concatenation prevents hidden performance bottlenecks in high‑throughput services.
OPTIMIZATION CHALLENGE
The key insight is to avoid repeated allocations by pre‑allocating a buffer of exact final size (2 × n) and writing both halves in a single pass, turning what could be a quadratic operation into a linear one.
REAL-WORLD CONNECTION
Think of a network protocol that sends a payload followed by its checksum computed on the reversed payload. The server must reconstruct the original message by concatenating the reversed checksum with the payload, mirroring the Reverse Encode pattern in a distributed system.
During an interview, write the solution using a mutable buffer first, then explain why you chose it over naive string concatenation—this demonstrates both coding skill and performance awareness.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Reverse Encode String problem belongs to the classic family of linear‑time string manipulation tasks. The core operation—reversing a sequence of characters—can be performed in‑place by swapping symmetric pairs, which yields a deterministic O(n) runtime where n is the length of the input. After the reversal, a simple concatenation of the reversed buffer with the original string produces the final output. Naïve solutions that repeatedly concatenate using immutable string objects (e.g., using the '+' operator inside a loop) trigger O(n²) time due to repeated allocation and copying of intermediate strings, which becomes prohibitive for inputs in the order of millions of characters. The optimal paradigm leverages a mutable buffer (such as a character array or StringBuilder) to construct the reversed segment once, then appends the original segment in a single pass, guaranteeing linear time and constant auxiliary space beyond the output itself.
From an algorithmic perspective, this problem illustrates the importance of understanding data‑structure characteristics—specifically, the difference between immutable strings and mutable buffers. By pre‑allocating a buffer of size 2 × n, we can write the reversed characters into the first half and the original characters into the second half without any extra copying. This approach also respects the requirement to return an empty string for null or undefined inputs, handling edge cases gracefully. The resulting solution is both time‑optimal (O(n)) and space‑optimal (O(n) for the output, O(1) auxiliary).
Interview Questions on This Problem
Q1How would you implement Reverse Encode String in a language where strings are immutable, such as Java or Python, while still achieving O(n) time?
Use a mutable builder like StringBuilder (Java) or a list of characters (Python). First, iterate from the end of the input string to the start, appending each character to the builder. Then, iterate from the start to the end, appending the original characters. Finally, convert the builder back to a string. This avoids repeated string concatenation and ensures linear time.
Q2What are the pitfalls of using the '+' operator inside a loop for this problem, and how does it affect memory usage?
Using '+' inside a loop creates a new string object on each iteration because strings are immutable. Each new string copies the entire accumulated content, leading to O(n²) time and O(n²) temporary memory allocations. This can cause out‑of‑memory errors for large inputs and dramatically slows down execution.
Q3Can you extend the Reverse Encode operation to work on a stream of characters (e.g., reading from a file) without loading the entire string into memory? Explain your approach.
Yes. First, read the entire stream to determine its length (or store characters in a temporary file). Then, write the characters to the output in reverse order by seeking from the end of the temporary storage, followed by a second pass that writes the original order. If random access is unavailable, you can use a double‑ended queue (deque) to push characters as they arrive and later pop from both ends, achieving O(n) time with O(n) auxiliary space limited to the deque.
Examples
Input
abc
Output
cbaabc
Explanation: Reverse of "abc" is "cba". Append original "abc" to get "cbaabc".
Input
Hello
Output
olleHHello
Explanation: Reverse of "Hello" is "olleH". Append original "Hello" to get "olleHHello".
Input
A
Output
AA
Explanation: Reverse of "A" is "A". Append original "A" to get "AA".
Input
Output
Explanation: Reversing an empty string yields an empty string. Appending the original empty string results in an empty string.
Input
null
Output
Explanation: When the input is null, the function returns an empty string as specified.
Constraints
- 0 <= s.length <= 100000
- s consists of printable ASCII characters
- The algorithm must run in O(n) time and use O(n) additional space where n is the length of s
Optimal Approach & Strategy
Allocate a mutable buffer of size 2 × n, fill the first half with characters from the end to the start, then fill the second half with the original order, achieving O(n) time and O(1) extra space.
Brute Force Approach
Repeatedly concatenate characters one by one while traversing the string forward and backward, which leads to O(n²) time due to repeated string copying.
Verified Code Solutions
/**
* @param {string} s
* @return {string}
*/
var reverseEncodeString = function(s) {
const reversed = s.split('').reverse().join('');
return reversed + s;
};class Solution {
public:
string reverseEncodeString(string s) {
string reversed = s;
reverse(reversed.begin(), reversed.end());
return reversed + s;
}
};class Solution {
public String reverseEncodeString(String s) {
StringBuilder reversed = new StringBuilder(s).reverse();
return reversed.toString() + s;
}
}class Solution:
def reverseEncodeString(self, s: str) -> str:
return s[::-1] + s/**
* @param {string} s
* @return {string}
*/
var reverseEncodeString = function(s) {
const reversed = s.split('').reverse().join('');
return reversed + s;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.