String Reversal Approaches in DSA Java

Mental Model

Reversing a string means flipping its characters so the last becomes first and the first becomes last.

Analogy: Imagine reading a sentence backwards, starting from the end and moving to the beginning, like rewinding a tape.

Original: h -> e -> l -> l -> o -> null
Reversed: o -> l -> l -> e -> h -> null

Dry Run Walkthrough

Input: string: "hello"

Goal: Reverse the string to get "olleh"

Step 1: Start with two pointers: left at 'h' (index 0), right at 'o' (index 4)

h [left] -> e -> l -> l -> o [right] -> null

Why: We need to swap characters from both ends moving towards the center

Step 2: Swap characters at left and right: 'h' and 'o'

o -> e -> l -> l -> h -> null

Why: Swapping first and last characters moves them to their reversed positions

Step 3: Move left pointer to 'e' (index 1), right pointer to 'l' (index 3)

o -> e [left] -> l -> l [right] -> h -> null

Why: Continue swapping inner characters to reverse the string fully

Step 4: Swap characters at left and right: 'e' and 'l'

o -> l -> l -> e -> h -> null

Why: Swapping inner characters continues the reversal

Step 5: Move left pointer to 'l' (index 2), right pointer to 'l' (index 2), pointers meet

o -> l -> l [left,right] -> e -> h -> null

Why: Pointers meet at center, reversal is complete

Result:

o -> l -> l -> e -> h -> null
Reversed string: "olleh"

Annotated Code

DSA Java

public class StringReversal {
    public static String reverseString(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = chars.length - 1;
        while (left < right) {
            // swap chars[left] and chars[right]
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++; // move left pointer right
            right--; // move right pointer left
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        String input = "hello";
        String reversed = reverseString(input);
        System.out.println(reversed);
    }
}

while (left < right) {

loop until pointers meet or cross to reverse characters

char temp = chars[left]; chars[left] = chars[right]; chars[right] = temp;

swap characters at left and right pointers

left++;

advance left pointer towards center

right--;

move right pointer towards center

Output

olleh

Complexity Analysis

Time: O(n) because we swap characters from both ends moving towards the center, touching each character once

Space: O(n) because we convert the string to a character array to modify it, which uses extra space proportional to input size

vs Alternative: Compared to creating a new string by concatenating characters from end to start (which can be O(n²) due to repeated string concatenation), this approach is more efficient

Edge Cases

empty string ""

returns empty string immediately without swaps

DSA Java

while (left < right) {

single character string "a"

returns the same single character string as reversal is itself

DSA Java

while (left < right) {

string with repeated characters "aaa"

swaps characters but result is same as input

DSA Java

while (left < right) {

When to Use This Pattern

When you need to reverse a string or array in place, look for two-pointer approach swapping from ends towards center for efficient reversal.

Common Mistakes

Mistake: Using string concatenation inside a loop to build reversed string causing O(n²) time
Fix: Use a character array and swap in place or use a StringBuilder and reverse method

Mistake: Not stopping the loop when pointers meet or cross, causing index errors
Fix: Use condition while (left < right) to stop at center

Summary

Reverses a string by swapping characters from both ends moving towards the center.

Use when you need to reverse strings efficiently without extra costly operations.

The key insight is using two pointers moving inward to swap characters in place.

Practice

1. Which of the following methods correctly reverses a string in Java using built-in functions?

easy

A. Using new StringBuilder(str).reverse().toString()

B. Using str.reverse()

C. Using str.toCharArray().reverse()

D. Using String.reverse(str)

Solution

1. Step 1: Understand Java String reversal methods

   Java's String class does not have a reverse() method, but StringBuilder does.

2. Step 2: Identify correct usage of StringBuilder

   Creating a StringBuilder from the string and calling reverse() then toString() returns the reversed string.

3. Final Answer:

   Using new StringBuilder(str).reverse().toString() -> Option A

4. Quick Check:

   StringBuilder.reverse() = correct reversal [OK]

Hint: Use StringBuilder's reverse() method for easy string reversal [OK]

Common Mistakes:

• Trying to call reverse() directly on String
• Using non-existent String.reverse() method
• Assuming toCharArray() has reverse() method

2. Which of the following code snippets correctly reverses a string str using a for loop in Java?

easy

A. for (int i = 0; i < str.length(); i++) reversed += str.charAt(i);

B. for (int i = 1; i <= str.length(); i++) reversed += str.charAt(i);

C. for (int i = str.length() - 1; i >= 0; i--) reversed += str.charAt(i);

D. for (int i = str.length(); i > 0; i--) reversed += str.charAt(i);

Solution

1. Step 1: Understand string indexing in Java

   String indices start at 0 and go to length()-1.

2. Step 2: Identify correct loop to reverse string

   Loop from last index (length()-1) down to 0, appending characters to reversed string.

3. Final Answer:

   for (int i = str.length() - 1; i >= 0; i--) reversed += str.charAt(i); -> Option C

4. Quick Check:

   Loop from end to start = correct reversal [OK]

Hint: Loop backward from length()-1 to 0 to reverse string [OK]

Common Mistakes:

• Looping forward instead of backward
• Using 1-based indexing instead of 0-based
• Accessing charAt with index equal to length()

3. What is the output of the following Java code?

String str = "hello";
String reversed = "";
for (int i = str.length() - 1; i >= 0; i--) {
    reversed += str.charAt(i);
}
System.out.println(reversed);

medium

A. hello

B. olleh

C. olle

D. SyntaxError

Solution

1. Step 1: Trace the for loop from end to start

   The loop starts at index 4 ('o') and goes down to 0 ('h'), appending each character to reversed.

2. Step 2: Build reversed string step-by-step

   Characters appended in order: 'o', 'l', 'l', 'e', 'h' forming "olleh".

3. Final Answer:

   olleh -> Option B

4. Quick Check:

   Reverse of "hello" = "olleh" [OK]

Hint: Appending chars backward builds reversed string [OK]

Common Mistakes:

• Expecting original string output
• Confusing loop direction
• Assuming syntax error due to += on strings

4. Identify the error in the following Java code that attempts to reverse a string:

String str = "world";
String reversed = "";
for (int i = 0; i <= str.length(); i++) {
    reversed += str.charAt(i);
}
System.out.println(reversed);

medium

A. No error, code runs correctly

B. String reversed should be a StringBuilder instead of String

C. Use str.reverse() instead of loop

D. Loop condition should be i < str.length() to avoid IndexOutOfBoundsException

Solution

1. Step 1: Check loop boundary conditions

   The loop runs from i=0 to i=str.length() inclusive, but valid indices are 0 to str.length()-1.

2. Step 2: Identify exception cause

   Accessing str.charAt(str.length()) causes IndexOutOfBoundsException.

3. Final Answer:

   Loop condition should be i < str.length() to avoid IndexOutOfBoundsException -> Option D

4. Quick Check:

   Index must be less than length() [OK]

Hint: Use i < length() in loops to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring exception from invalid index
• Assuming StringBuilder is mandatory

5. Given a string str, which approach efficiently reverses it without using extra space for another string in Java?

hard

A. Convert to char array, swap characters from ends moving inward, then create new string

B. Use StringBuilder.reverse() which creates a new reversed string internally

C. Concatenate characters in reverse order using a loop and a new string

D. Use recursion to build reversed string by concatenation

Solution

1. Step 1: Understand in-place reversal concept

   Strings in Java are immutable, so we cannot change them directly, but char arrays can be modified in place.

2. Step 2: Use char array swapping to reverse without extra string

   Convert string to char array, swap characters from start and end moving inward, then create string from modified array.

3. Step 3: Compare with other options

   Other methods create new strings or use extra space, so not in-place.

4. Final Answer:

   Convert to char array, swap characters from ends moving inward, then create new string -> Option A

5. Quick Check:

   In-place reversal uses char array swaps [OK]

Hint: Use char array swaps for in-place string reversal [OK]

Common Mistakes:

• Assuming StringBuilder.reverse() is in-place
• Using string concatenation causing extra space
• Ignoring string immutability in Java