String Reversal Approaches in DSA C++

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 string:
H -> e -> l -> l -> o -> null

Reversed string:
o -> l -> l -> e -> H -> null

Dry Run Walkthrough

Input: string: "hello"

Goal: Reverse the string so it reads "olleh"

Step 1: swap first and last characters ('h' and 'o')

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

Why: swap outer characters to start reversing from the ends

Step 2: swap second and second last characters ('e' and 'l')

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

Why: continue swapping moving inward to reverse the string

Step 3: middle character 'l' remains same as it's center

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

Why: middle character does not need swapping in odd length string

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <string>

// Function to reverse a string in place
void reverseString(std::string &s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        std::swap(s[left], s[right]); // swap characters at left and right
        left++; // move left pointer inward
        right--; // move right pointer inward
    }
}

int main() {
    std::string s = "hello";
    reverseString(s);
    std::cout << s << std::endl; // print reversed string
    return 0;
}

while (left < right) {

loop until pointers meet or cross to cover all swaps

std::swap(s[left], s[right]);

swap characters at current left and right positions

left++;

move left pointer one step inward

right--;

move right pointer one step inward

Output

olleh

Complexity Analysis

Time: O(n) because each character is visited once during swapping

Space: O(1) because reversal is done in place without extra storage

vs Alternative: Compared to creating a new reversed string (O(n) time and space), this approach saves memory by swapping in place

Edge Cases

empty string ""

function returns immediately with no changes

DSA C++

while (left < right) {

single character string "a"

no swaps occur since left is not less than right

DSA C++

while (left < right) {

string with all same characters "aaa"

swaps happen but characters remain same, string unchanged

DSA C++

std::swap(s[left], s[right]);

When to Use This Pattern

When asked to reverse a string or array in place, use two pointers from ends moving inward to swap elements efficiently.

Common Mistakes

Mistake: Using a loop that goes through the entire string length causing double swaps
Fix: Only loop until left pointer is less than right pointer to avoid undoing swaps

Mistake: Creating a new string instead of reversing in place when memory is limited
Fix: Use two-pointer swapping to reverse the string without extra space

Summary

Reverses a string by swapping characters from the ends moving inward.

Use when you need to reverse strings efficiently without extra memory.

The key insight is swapping pairs from outside to inside until pointers meet.

Practice

1. What does the std::reverse function do when applied to a string in C++?

easy

A. It reverses the order of characters in the string.

B. It sorts the characters in ascending order.

C. It removes all vowels from the string.

D. It converts all characters to uppercase.

Solution

1. Step 1: Understand std::reverse behavior

   The std::reverse function reverses the order of elements in a range, here characters in a string.

2. Step 2: Apply to string

   When applied to a string, it changes the string so the last character becomes first, and so on.

3. Final Answer:

   It reverses the order of characters in the string. -> Option A

4. Quick Check:

   std::reverse reverses string characters [OK]

Hint: std::reverse flips string characters in place [OK]

Common Mistakes:

• Thinking std::reverse sorts characters
• Confusing reversal with uppercase conversion
• Assuming it removes characters

2. Which of the following is the correct syntax to reverse a string s using std::reverse in C++?

easy

A. std::reverse(s.begin(), s.end());

B. std::reverse(s, 0, s.length());

C. reverse(s.begin(), s.end());

D. std::reverse(s.start(), s.finish());

Solution

1. Step 1: Identify correct std::reverse usage

   The std::reverse function requires two iterators: start and end of the range.

2. Step 2: Match syntax with string iterators

   For string s, s.begin() and s.end() provide correct iterators.

3. Final Answer:

   std::reverse(s.begin(), s.end()); -> Option A

4. Quick Check:

   std::reverse needs begin and end iterators [OK]

Hint: Use s.begin() and s.end() with std::reverse [OK]

Common Mistakes:

• Using incorrect iterator names like start() or finish()
• Calling reverse without std:: prefix
• Passing string and indices directly

3. What will be the output of the following C++ code?

std::string s = "hello";
for (int i = 0; i < s.length() / 2; ++i) {
    std::swap(s[i], s[s.length() - 1 - i]);
}
std::cout << s;

medium

A. hello

B. helol

C. olleh

D. error

Solution

1. Step 1: Understand the swapping loop

   The loop swaps characters from start and end moving towards the center, effectively reversing the string.

2. Step 2: Trace the swaps on "hello"

   Swap s[0] and s[4]: 'h' and 'o' -> "oellh"; Swap s[1] and s[3]: 'e' and 'l' -> "olleh".

3. Final Answer:

   olleh -> Option C

4. Quick Check:

   Swapping pairs reverses string [OK]

Hint: Swapping pairs from ends reverses string [OK]

Common Mistakes:

• Not swapping correctly causing partial reversal
• Loop running too many or too few times
• Confusing indices causing wrong output

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

for (int i = 0; i <= s.length() / 2; ++i) {
    std::swap(s[i], s[s.length() - i]);
}

medium

A. No error; code correctly reverses the string.

B. The second index should be s.length() - 1 - i instead of s.length() - i to avoid out-of-range access.

C. The loop should start from i = 1 instead of 0.

D. std::swap cannot be used with string characters.

Solution

1. Step 1: Check the swap indices

   The code uses s[s.length() - i]. For i=0, this accesses s[s.length()], out of bounds.

2. Step 2: Correct reversal index

   To reverse, swap s[i] with s.length() - 1 - i.

3. Final Answer:

   The second index should be s.length() - 1 - i instead of s.length() - i to avoid out-of-range access. -> Option B

4. Quick Check:

   Missing -1 in second index causes out-of-range [OK]

Hint: Check indices carefully to avoid out-of-range errors [OK]

Common Mistakes:

• Off-by-one error: s.length() - i instead of s.length() - 1 - i
• Incorrect index calculation for swap
• Assuming std::swap can't swap chars

5. Given a string s, which approach below correctly reverses the string without using extra space and handles empty strings safely?

hard

A. Use a while loop swapping characters until i > s.length().

B. Use std::reverse(s.begin(), s.end() - 1); to reverse all but last character.

C. Create a new string and append characters from end to start.

D. Use a for loop swapping characters from start to end with condition i < s.length() / 2.

Solution

1. Step 1: Analyze each approach

   Use a for loop swapping characters from start to end with condition i < s.length() / 2. swaps characters in place up to half length, safe for empty strings. Use std::reverse(s.begin(), s.end() - 1); to reverse all but last character. misses last character. Create a new string and append characters from end to start. uses extra space. Use a while loop swapping characters until i > s.length(). has wrong loop condition.

2. Step 2: Confirm correctness and safety

   Use a for loop swapping characters from start to end with condition i < s.length() / 2. reverses string in place without extra space and works for empty strings as loop won't run.

3. Final Answer:

   Use a for loop swapping characters from start to end with condition i < s.length() / 2. -> Option D

4. Quick Check:

   In-place swap up to half length reverses string safely [OK]

Hint: Swap pairs up to half length for safe in-place reversal [OK]

Common Mistakes:

• Using incorrect end iterator causing partial reversal
• Creating new string uses extra space
• Wrong loop conditions causing infinite loops