String Reversal Approaches in DSA C++ - Execution Trace

Concept Flow - String Reversal Approaches

Start with original string

↓

Choose reversal method

↓

Method 1

↓

Reverse string

↓

Return reversed string

↓

End

The flow starts with the original string, then chooses one of several reversal methods, reverses the string, and returns the reversed result.

Execution Sample

DSA C++

std::string reverseString(std::string s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        std::swap(s[left], s[right]);
        left++; right--;
    }
    return s;
}

This code reverses a string by swapping characters from the start and end moving towards the center.

Execution Table

Step	Operation	left	right	String State	Action
1	Initialize pointers	0	4	"hello"	Set left=0, right=4
2	Swap s[left] and s[right]	0	4	"oellh"	Swap 'h' and 'o'
3	Increment left, decrement right	1	3	"oellh"	left=1, right=3
4	Swap s[left] and s[right]	1	3	"olleh"	Swap 'e' and 'l'
5	Increment left, decrement right	2	2	"olleh"	left=2, right=2
6	Check condition left < right	2	2	"olleh"	Condition false, stop
7	Return reversed string	-	-	"olleh"	Return result

💡 left equals right (2 == 2), condition left < right is false, loop ends

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	Final
left	0	1	2	2	2
right	4	3	2	2	2
s (string)	"hello"	"oellh"	"olleh"	"olleh"	"olleh"

Key Moments - 3 Insights

Why do we stop swapping when left equals right?

Because when left equals right, the middle character is reached and swapping it with itself is unnecessary, as shown in step 6 where left=2 and right=2, condition left < right is false.

What happens if the string length is odd?

The middle character stays in place without swapping, as the pointers meet at the center (step 6), so the reversal is complete without extra swaps.

Why do we swap characters instead of creating a new string?

Swapping in place saves memory and time by modifying the original string directly, as seen in steps 2 and 4 where characters are swapped without extra storage.

Visual Quiz - 3 Questions

Look at the execution table, what is the string state after step 4?

A "olleh"

B "oellh"

C "hello"

D "hlelo"

💡 Hint

Check the 'String State' column in row for step 4 in the execution_table.

At which step does the condition left < right become false?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at the 'Action' column in the execution_table where the loop stops.

If the string was "abcd", what would be the string state after the first swap?

A "dbca"

B "bacd"

C "dbcd"

D "dcba"

💡 Hint

Consider swapping first and last characters of "abcd" as in step 2 of the execution_table.

Concept Snapshot

String Reversal Approaches:
- Use two pointers: left at start, right at end
- Swap characters at left and right
- Move pointers inward until they meet or cross
- Works in-place, no extra memory needed
- Stops when left >= right

Full Transcript

This visualization shows how to reverse a string by swapping characters from the ends moving inward. We start with two pointers, left at 0 and right at the last index. At each step, we swap the characters at these pointers, then move left forward and right backward. This continues until left is no longer less than right, meaning we have reversed the entire string. The example uses the string "hello" and shows each swap and pointer movement until the reversed string "olleh" is returned.

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