Reverse Prefix of Word - Solution & Explanation
Problem Statement
Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.
- For example, if
word = "abcdefd"andch = "d", then you should reverse the segment that starts at0and ends at3(inclusive). The resulting string will be"dcbaefd".
Return the resulting string.
Example 1:
Input: word = "abcdefd", ch = "d" Output: "dcbaefd" Explanation: The first occurrence of "d" is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".
Example 2:
Input: word = "xyxzxe", ch = "z" Output: "zxyxxe" Explanation: The first and only occurrence of "z" is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".
Example 3:
Input: word = "abcd", ch = "z" Output: "abcd" Explanation: "z" does not exist in word. You should not do any reverse operation, the resulting string is "abcd".
Constraints:
1 <= word.length <= 250wordconsists of lowercase English letters.chis a lowercase English letter.
Approach Overview
Problem Overview: Given a string word and a character ch, reverse the substring from the start of the string up to the first occurrence of ch. If the character does not exist in the string, return the original word unchanged.
Approach 1: Brute Force with Stack (O(n) time, O(n) space)
The straightforward method scans the string to locate the first index of ch. Once found, push characters from index 0 through that index into a stack. Pop elements from the stack to build the reversed prefix, then append the remainder of the string unchanged. The stack naturally reverses order through LIFO operations. This approach is simple to reason about and clearly demonstrates the prefix reversal logic, though it requires extra memory proportional to the prefix length.
This technique works well if you are already comfortable with stack-based reversal patterns. However, the additional memory allocation is unnecessary because the operation can be performed directly on the string or character array.
Approach 2: Two Pointers (O(n) time, O(1) space)
The optimal solution first finds the index of the first occurrence of ch by iterating through the string once. If the character exists, reverse the prefix between indices 0 and idx using the classic two pointers pattern. Initialize one pointer at the beginning and the other at the found index, then swap characters while moving both pointers toward the center.
This method performs the reversal in-place on the character array representation of the string. Each character participates in at most one swap, so the total work remains linear. The key insight is that you only need to reverse a single contiguous segment rather than constructing a new string.
Recommended for interviews: The two pointers approach is what interviewers expect. It shows you recognize a classic in-place reversal pattern and can reduce auxiliary space to O(1). Explaining the brute force stack method first demonstrates understanding of the problem mechanics, but implementing the two-pointer reversal shows stronger algorithmic judgment.
Approach 1: Brute Force Approach
The brute force approach involves scanning the string to find the index of the first occurrence of the character and then reversing the substring from the start to that index. If the character is not found, the string remains unchanged. This approach makes use of two operations: the indexOf operation which finds the index of the first occurrence of the character and a reversing operation for the substring.
In this C solution, we first calculate the length of the string. We traverse the string to find the index of the first occurrence of the specified character. If found, we perform a reversal of the substring from start to the found index. The reversed substring is then copied back to a new result string.
Complexity
The time complexity is O(n) due to the search and reversal operations. The space complexity is O(n) for the storage of the resulting string.
Approach 2: Two Pointers Approach
The two-pointers approach is an efficient way to handle the reversed segment directly without using extra space for substring operations. This method entails finding the index of the character first and then reversing the required part of the string in place (where applicable), by gradually swapping elements from both ends of the segment moving inwards.
This C solution utilizes a helper function to reverse a part of the array in place. We locate the index as before, then swap elements utilizing two pointers starting from both ends of the range and working inwards.
Complexity
The time complexity remains O(n) for the search and in-place reversal. The space complexity is O(1) since no extra space proportional to input size is used.
Approach 3: Simulation
First, we find the index i where the character ch first appears. Then, we reverse the characters from index 0 to index i (including index i). Finally, we concatenate the reversed string with the string starting from index i + 1.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string word.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n) due to the search and reversal operations. The space complexity is O(n) for the storage of the resulting string. |
| Two Pointers Approach | The time complexity remains O(n) for the search and in-place reversal. The space complexity is O(1) since no extra space proportional to input size is used. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Stack | O(n) | O(n) | Useful for understanding prefix reversal logic or when demonstrating stack-based string manipulation. |
| Two Pointers (Optimal) | O(n) | O(1) | Best for interviews and production code when you want an in-place reversal without extra memory. |
Video Solution
Reverse Prefix of Word (LeetCode 2000) | Full Solution with stack data structure • Nikhil Lohia • 2,775 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse Prefix of Word easy or hard?
Reverse Prefix of Word Python/Java solution
How to solve Reverse Prefix of Word in O(n)?
What is the best approach for Reverse Prefix of Word?
Is Reverse Prefix of Word asked at Google/Amazon/Meta?
What data structure is used in Reverse Prefix of Word?
What is the time complexity of Reverse Prefix of Word?
Ready to solve this problem?
Practice Reverse Prefix of Word with our built-in code editor and test cases.
Practice on FleetCode