Reverse String II in JavaScript (O(n^2) Time Complexity)

Input:  "hello"

Output: "olleh"

Understanding the Problem

The core challenge of this problem is to reverse a given string without using any built-in functions or libraries. This means we need to manually manipulate the string to achieve the desired result.

Reversing a string is a common problem in computer science with applications in data processing, text manipulation, and more. A common pitfall is to rely on built-in functions, which is not allowed in this problem.

Approach

To solve this problem, we need to think about how to manually reverse a string. A naive approach might involve swapping characters from the beginning and end of the string until we reach the middle. However, this problem specifically requires an O(n^2) time complexity, which suggests a less efficient method.

Naive Solution

A naive solution would involve creating a new string and appending characters from the original string in reverse order. This approach is not optimal because it involves repeatedly concatenating strings, which is an O(n) operation in JavaScript. Therefore, the overall time complexity becomes O(n^2).

Optimized Solution

Even though the problem requires an O(n^2) solution, let's discuss a more efficient approach for educational purposes. An optimized solution would involve swapping characters in place, resulting in O(n) time complexity. However, we will focus on the O(n^2) solution as required.

Algorithm

Here is a step-by-step breakdown of the O(n^2) algorithm:

1. Initialize an empty string to store the reversed string.
2. Iterate through the original string from the last character to the first character.
3. For each character, append it to the new string.
4. Return the new string.

Code Implementation

// Function to reverse a string without using built-in functions
function reverseString(str) {
  // Initialize an empty string to store the reversed string
  let reversedStr = '';
  
  // Iterate through the original string from the last character to the first character
  for (let i = str.length - 1; i >= 0; i--) {
    // Append each character to the new string
    reversedStr += str[i];
  }
  
  // Return the new string
  return reversedStr;
}

// Example usage
const input = "hello";
const output = reverseString(input);
console.log(output); // Output: "olleh"

Complexity Analysis

The time complexity of this approach is O(n^2) because string concatenation in JavaScript is an O(n) operation, and we are performing it n times. The space complexity is O(n) because we are storing the reversed string.

Edge Cases

Let's consider some edge cases:

• Empty string: The function should return an empty string.
• Single character string: The function should return the same character.
• String with spaces: The function should correctly reverse the string, including spaces.

Examples:

Input: ""
Output: ""

Input: "a"
Output: "a"

Input: "a b c"
Output: "c b a"

Testing

To test the solution comprehensively, we should include a variety of test cases:

• Simple strings
• Strings with spaces
• Empty strings
• Strings with special characters

Example test cases:

console.log(reverseString("hello")); // "olleh"
console.log(reverseString("a b c")); // "c b a"
console.log(reverseString("")); // ""
console.log(reverseString("a")); // "a"
console.log(reverseString("12345")); // "54321"

Thinking and Problem-Solving Tips

When approaching such problems, it's important to:

• Understand the constraints and requirements.
• Think about different approaches and their trade-offs.
• Break down the problem into smaller, manageable parts.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to reverse a string without using built-in functions or libraries. We explored a naive O(n^2) solution, provided a detailed algorithm, and implemented the solution in JavaScript. Understanding and solving such problems is crucial for developing strong problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Reverse String
• GeeksforGeeks: Reverse a String in Place
• HackerRank: Reverse a String