Ace The Interview: How to Reverse a String Without Using Built-In Methods

Reversing a string without using built-in methods is a common interview question that tests your understanding of basic algorithms. In this blog, we’ll walk through how to reverse a string manually using several approaches, provide visuals for each, and discuss the trade-offs of each solution to help you understand their strengths and weaknesses.

Understanding the Problem

The problem is simple: given a string, return the reverse of the string without using any built-in methods like split(), reverse(), or join().

For example:

Input:  "hello"
Output: "olleh"

Approach 1: Using a Loop (Iterative Solution)

Description:

The loop-based solution iterates through the string from the last character to the first, appending each character to a new string.

Code Example:

function reverseString(str) {
  let reversed = '';
  for (let i = str.length - 1; i >= 0; i--) {
    reversed += str[i];
  }
  return reversed;
}

Visual:

graph TD;
    A[Input: "hello"] --> B(Loop i from str.length - 1 to 0);
    B --> C[reversed = ""];
    C --> D[Append str[4] = "o"];
    D --> E[Append str[3] = "l"];
    E --> F[Append str[2] = "l"];
    F --> G[Append str[1] = "e"];
    G --> H[Append str[0] = "h"];
    H --> I[Result: "olleh"];

Trade-offs (Pros & Cons)

• Pros:
• Simple and intuitive: Easy to understand and implement, making it great for beginners.
• Efficient: Linear time complexity O(n) with respect to the string length.
• No additional space required for pointers: Unlike two-pointer techniques, no complex structures are needed.

• Cons:
• String concatenation inefficiency: String concatenation in each loop iteration may lead to performance issues with large strings in languages where string concatenation is costly (e.g., Python).
• Memory usage: Allocates new memory for the reversed string as it grows.

Approach 2: Using a Two-Pointer Technique

Description:

The two-pointer technique involves using two pointers, one at the beginning and one at the end of the array, swapping characters in place.

Code Example:

function reverseString(str) {
  let arr = str.split('');
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }

  return arr.join('');
}

Visual:

graph TD;
    A[Input: "world"] --> B(Initial array: ['w', 'o', 'r', 'l', 'd']);
    B --> C[Left = 0, Right = 4];
    C --> D(Swap arr[0] and arr[4]);
    D --> E[Array after swap: ['d', 'o', 'r', 'l', 'w']];
    E --> F[Left = 1, Right = 3];
    F --> G(Swap arr[1] and arr[3]);
    G --> H[Array after swap: ['d', 'l', 'r', 'o', 'w']];
    H --> I[Left = 2, Right = 2];
    I --> J[End of loop: Return 'dlrow'];

Trade-offs (Pros & Cons)

• Pros:
• In-place operation: This solution is space-efficient because it reverses the string in place without allocating additional space for a new string.
• Efficient: Linear time complexity O(n).
• Memory-efficient: Uses a constant amount of extra memory, O(1), for the two pointers and temporary variable for swapping.

• Cons:
• String immutability in JavaScript: This approach requires converting the string to an array (O(n) space) and then converting it back to a string. If immutability weren’t an issue (like in C), this would be truly space-efficient.
• More complex than a loop: Introduces additional pointer logic, which can be slightly harder to read and understand for beginners.

Approach 3: Recursive Solution

Description:

The recursive solution works by breaking down the problem into smaller sub-problems. The first character is processed and appended to the reversed result of the remaining string.

Code Example:

function reverseString(str) {
  if (str === '') {
    return str;
  }

  return reverseString(str.slice(1)) + str[0];
}

Visual:

graph TD;
    A[Input: "recursion"] --> B[reverseString("recursion")];
    B --> C[reverseString("ecursion") + "r"];
    C --> D[reverseString("cursion") + "e"];
    D --> E[reverseString("ursion") + "c"];
    E --> F[reverseString("rsion") + "u"];
    F --> G[reverseString("sion") + "r"];
    G --> H[reverseString("ion") + "s"];
    H --> I[reverseString("on") + "i"];
    I --> J[reverseString("n") + "o"];
    J --> K[reverseString("") + "n"];
    K --> L[Result: "noisrucer"];

Trade-offs (Pros & Cons)

• Pros:
• Elegant and clean: Recursion leads to a clean and elegant solution for simple problems.
• Natural division of problems: Recursion is a natural fit for problems that can be broken into smaller sub-problems like reversing strings.

• Cons:
• Stack overflow risk: If the string is large, the recursion depth could exceed the call stack limit, leading to a stack overflow. The space complexity is O(n) due to the recursive call stack.
• Less efficient: It may have worse performance due to the overhead of function calls, especially for larger strings.
• Harder to understand: Recursion can be more difficult to grasp and debug for beginners.

Approach 4: Using a Stack (Simulating the Call Stack)

Description:

This approach uses a stack, a last-in, first-out (LIFO) data structure, to reverse the string by pushing characters onto the stack and popping them off in reverse order.

Code Example:

function reverseString(str) {
  const stack = [];

  for (let i = 0; i < str.length; i++) {
    stack.push(str[i]);
  }

  let reversed = '';

  while (stack.length > 0) {
    reversed += stack.pop();
  }

  return reversed;
}

Visual:

graph TD;
    A[Input: "stack"] --> B(Push characters to stack);
    B --> C[Stack: ['s', 't', 'a', 'c', 'k']];
    C --> D[Pop 'k' from stack];
    D --> E[Pop 'c' from stack];
    E --> F[Pop 'a' from stack];
    F --> G[Pop 't' from stack];
    G --> H[Pop 's' from stack];
    H --> I[Result: "kcats"];

Trade-offs (Pros & Cons)

• Pros:
• Simple concept: The stack approach is intuitive because of the natural LIFO (Last In, First Out) behavior, which fits well with reversing operations.
• Good for teaching: Useful for demonstrating how data structures like stacks can be used in algorithms.

• Cons:
• Additional space required: A new data structure (stack) is used to store characters, so the space complexity is O(n), which is not as space-efficient as the in-place two-pointer approach.
• More overhead: Slight overhead from pushing to and popping from the stack.

Interview Tips for Reversing a String

• Clarify Requirements: Always clarify with the interviewer whether you can use built-in methods. If not, pick the appropriate approach.

• Explain Your Solution: Walk the interviewer through your thought process, explaining the logic behind each step.

• Optimize Your Code: Once you’ve implemented the basic solution, discuss potential optimizations, such as reducing space complexity or improving readability.

Conclusion

Reversing a string without using built-in methods is a classic interview problem that tests your understanding of algorithms and data structures. Whether you choose to use iteration, recursion, two-pointers, or stacks, each approach comes with its own trade-offs in terms of performance, memory, and complexity.

Understanding these trade-offs will help you select the right approach for the problem at hand and demonstrate a deeper knowledge of algorithms in interviews.