Watch 10 video solutions for Reverse Prefix of Word, a easy level problem involving Two Pointers, String, Stack. This walkthrough by codestorywithMIK has 3,711 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (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 <= 250word consists of lowercase English letters.ch is a lowercase English letter.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 | 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. |