Reverse String III in JavaScript with O(n) Time Complexity

Input:  "hello"

Output: "olleh"

Problem Definition

The task is to reverse a given string without using any built-in functions or libraries. The input is a single string, and the output should be the reversed version of that string.

Input: A string s of length n.

Output: A string which is the reverse of s.

Constraints:

• The algorithm should run in O(n) time.
• The algorithm should use O(n) extra space.

Example:

Input: "hello"
Output: "olleh"

Understanding the Problem

The core challenge is to reverse the string efficiently without using built-in functions. This problem is significant in understanding basic string manipulation and memory management. Common applications include text processing and data transformation.

Potential pitfalls include misunderstanding the constraints and attempting to use built-in functions, which is not allowed.

Approach

To solve this problem, we need to think about how to reverse a string manually. A naive solution might involve iterating through the string and constructing the reversed string character by character. However, this approach might not be optimal in terms of space and time complexity.

We can optimize this by using a two-pointer technique:

• Initialize two pointers, one at the start and one at the end of the string.
• Swap the characters at these pointers and move the pointers towards the center.
• Continue this process until the pointers meet in the middle.

This approach ensures that we only traverse the string once, achieving O(n) time complexity, and we use O(n) extra space to store the reversed string.

Algorithm

Here is a step-by-step breakdown of the algorithm:

1. Initialize an empty array to store the reversed string.
2. Use a for loop to iterate through the string from the end to the beginning.
3. Append each character to the array.
4. Join the array into a single string and return it.

Code Implementation

/**
 * Function to reverse a string without using built-in functions
 * @param {string} s - The input string
 * @return {string} - The reversed string
 */
function reverseString(s) {
    // Initialize an empty array to store the reversed string
    let reversedArray = [];
    
    // Iterate through the string from the end to the beginning
    for (let i = s.length - 1; i >= 0; i--) {
        // Append each character to the array
        reversedArray.push(s[i]);
    }
    
    // Join the array into a single string and return it
    return reversedArray.join('');
}

// Example usage
console.log(reverseString("hello")); // Output: "olleh"

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. We traverse the string once.

Space Complexity: O(n), as we use an array to store the reversed string.

Compared to a naive approach, this method is efficient in both time and space.

Edge Cases

Consider the following edge cases:

• Empty string: The output should be an empty string.
• Single character string: The output should be the same as the input.
• Strings with spaces and special characters: Ensure these are handled correctly.

Examples:

Input: ""
Output: ""

Input: "a"
Output: "a"

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

Testing

To test the solution comprehensively, consider a variety of test cases:

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

Example test cases:

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

Thinking and Problem-Solving Tips

When approaching such problems:

• Break down the problem into smaller parts.
• Think about the constraints and how they affect your solution.
• Consider edge cases and how to handle them.
• Practice similar problems to improve your problem-solving skills.

Conclusion

Reversing a string without using built-in functions is a fundamental problem that helps in understanding basic string manipulation and algorithm design. By following the approach and algorithm discussed, you can efficiently solve this problem with O(n) time complexity and O(n) space complexity.

Practice and explore further to enhance your skills and understanding.

Additional Resources

• MDN Web Docs: String
• LeetCode: Reverse String
• GeeksforGeeks: Reverse a String in Java