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.
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.
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.
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.
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.
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.
| 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 | — |
| 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. |
Reverse Prefix of Word | Detail on reverse Function | Leetcode 2000 | codestorywithMIK • codestorywithMIK • 3,711 views views
Watch 9 more video solutions →Practice Reverse Prefix of Word with our built-in code editor and test cases.
Practice on FleetCode