Reverse Until Character

Introduction

Welcome to the final lesson in our module on core in-place manipulation techniques. Having mastered reversing entire arrays, specific segments, and even the order of words, we now address a scenario where the reversal boundary is dynamic. Today's objective is to solve the "Reverse Prefix of Word" problem: reversing the initial segment of a string up to the first occurrence of a specific character.

This task, common in coding challenges like LeetCode #2000, combines searching with the reversal skills you've built. It requires you to first find a specific index and then apply a reversal to the substring preceding it.

Let's begin with a clear visual of the problem statement.

This diagram illustrates the task: find the first 'd' at index 3, reverse the prefix 'abcd' to 'dcba', and append the rest of the string 'efd'.

The Core Logic: Find and Reverse

The problem naturally decomposes into two steps:

Find the Boundary: Locate the index of the first occurrence of the character ch.
Reverse the Prefix: Reverse the segment of the string from the beginning (index 0) up to and including that found index.

An important edge case is when ch does not exist in the string. In this situation, no action is taken.

In Python, we can tackle this very efficiently by leveraging built-in string methods and slicing. The algo.monster article provides a clear, step-by-step guide to this approach.

2000. Reverse Prefix of Word - In-Depth Explanation

This guide walks through the most direct and Pythonic way to solve the problem, using str.find() and string slicing.

Please read the following sections to understand the logic and its implementation: Problem Description and Intuition: This will solidify your understanding of the problem and the high-level plan. Solution Approach: Pay close attention to how find() is used to get the index and how slicing (word[i::-1]) elegantly reverses the prefix. Example Walkthrough: Trace the example word = "abcdefd", ch = "d" to see the steps in action.

As you've seen, Python's str.find(ch) is perfect for this task. It returns the index of the first occurrence of ch or -1 if ch is not found, neatly handling our main case and the edge case in one call. In contrast, str.index(ch) would raise a ValueError if the character isn't found, requiring a try...except block, making it less convenient here.

Implementation: Slicing vs. Two-Pointers

There are two primary ways to implement the reversal part in Python, each with its own trade-offs.

1. The Pythonic Slicing Approach

This is the method detailed in the algo.monster resource. Once you find the index k, the solution is a concise one-liner:
reversed_prefix = word[:k+1][::-1] or more simply word[k::-1]
suffix = word[k+1:]
result = reversed_prefix + suffix

This is highly readable and leverages Python's optimized internal C implementations for slicing, making it very performant. However, since Python strings are immutable, this approach creates new string objects for the prefix, the suffix, and the final result. Therefore, its space complexity is O(N), where N is the length of the string.

The code and complexity analysis from algo.monster summarize this perfectly.

2000. Reverse Prefix of Word - In-Depth Explanation

This material provides the final code, analyzes its efficiency, and highlights common mistakes.

First, review the Solution Implementation to see the complete, clean Python code. Next, read the Time and Space Complexity section. Confirm your understanding that both time and space are linear due to the search and string creation. Finally, look over the Common Pitfalls. The points on off-by-one errors in slicing and forgetting the "not found" case are particularly important.

2. The "In-Place" Two-Pointer Approach

Connecting to our previous lessons on in-place reversal, we can also use the two-pointer technique. Since strings are immutable, a true in-place swap isn't possible. Instead, we perform the swaps on a mutable version of the string, typically a list of characters.

The steps are:

Find the index k of the character ch.
Convert the string to a list: word_list = list(word).
Initialize two pointers, left = 0 and right = k.
Swap word_list[left] and word_list[right], then increment left and decrement right until they meet.
Join the list back into a string: ''.join(word_list).

This approach mirrors the low-level logic you'd use in languages with mutable strings like C++. While it involves the overhead of list conversion in Python, understanding this pattern is crucial as it's a fundamental algorithm.

The LearnYard resource provides a great explanation and implementation of this two-pointer method.

Reverse Prefix of Word - LearnYard

This resource demonstrates how to apply the two-pointer reversal pattern to this problem, accounting for Python's string immutability.

Read the section on the Optimal Approach. Focus on the intuition of swapping characters and the step-by-step process. Then, examine the provided Python code block to see how it's implemented using a list.

For most Python interview scenarios, the slicing method is preferred for its conciseness and efficiency. However, being able to articulate the two-pointer alternative demonstrates a deeper understanding of the underlying reversal algorithm.

Conclusion

In this lesson, you've learned how to reverse a string prefix based on a dynamically located character. This completes our module on fundamental in-place and string reversal techniques.

Here are the key takeaways:

Problem Decomposition: The task is a two-step process of finding a boundary and then applying a reversal.
Method Selection: In Python, str.find() is the ideal tool for locating the boundary index due to its handling of the "not found" case.
Implementation Trade-offs:
- Slicing is the most Pythonic, concise, and often fastest method, though it uses O(N) space.
- Two-pointers on a list is a valid alternative that demonstrates the core in-place reversal algorithm, despite the overhead of type conversion in Python.

You are now well-equipped to handle a variety of reversal problems on strings and arrays.

Our next module will shift gears to a different domain: Integer and Bitwise Operations. We will begin by tackling a problem analogous to string reversal—reversing the digits of an integer—where you'll need to consider new constraints like numerical overflow.