To solve this problem, reverse the prefix of the string from index 0 to the index of the first occurrence of the target character. If the character does not exist, return the string unchanged. The two-pointer approach is effective for scanning and performing the required operation.
Problem Statement
Given a string 'word' and a character 'ch', reverse the segment of 'word' that starts from index 0 and ends at the index of the first occurrence of 'ch'. If 'ch' does not exist in 'word', the string remains unchanged.
Return the resulting string after performing the above reversal operation.
Examples
Example 1
Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
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"
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"
"z" does not exist in word. You should not do any reverse operation, the resulting string is "abcd".
Constraints
- 1 <= word.length <= 250
- word consists of lowercase English letters.
- ch is a lowercase English letter.
Solution Approach
Two-pointer scanning
Use two pointers to locate the first occurrence of the character 'ch' and reverse the portion of the string from the start to that index. This approach ensures optimal traversal of the string.
In-place reversal
Once the target index is found, reverse the substring in place using the two-pointer technique, which eliminates the need for extra space and ensures efficient time complexity.
Handle missing character case
If the character 'ch' is not found, simply return the string unchanged. The algorithm should handle this case without performing any unnecessary operations.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
The time complexity is O(n) because we scan the string once to locate the first occurrence of 'ch' and potentially reverse part of the string. The space complexity is O(n) due to the space required for the result string.
What Interviewers Usually Probe
- Candidate can quickly identify the problem's two-pointer scanning approach.
- Candidate efficiently handles cases where the target character does not exist in the string.
- Candidate implements the in-place reversal technique without using unnecessary extra space.
Common Pitfalls or Variants
Common pitfalls
- Failing to handle the case where the target character does not exist in the string.
- Not reversing the string in place, leading to extra space usage.
- Overcomplicating the solution by using additional data structures instead of two-pointer scanning.
Follow-up variants
- Consider handling multiple occurrences of the target character and reversing up to the last occurrence.
- Extend the problem by allowing the user to reverse the segment up to a specified index instead of just the first occurrence.
- Consider reversing substrings from any starting index to a given character index.
How GhostInterview Helps
- GhostInterview assists by identifying the correct approach: two-pointer scanning with invariant tracking.
- With problem-specific hints, GhostInterview helps candidates focus on the key aspects of the solution, such as handling the edge case of a missing character.
- GhostInterview ensures efficient solution generation by promoting in-place reversal and optimal space usage.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the time complexity of the Reverse Prefix of Word problem?
The time complexity is O(n), where n is the length of the string 'word'. This is because we scan the string once to locate the target character and reverse the necessary part of the string.
How do you handle the case when the character does not exist in the string?
If the target character is not found in the string, the function returns the string unchanged, without performing any reversal.
What is the space complexity of this solution?
The space complexity is O(n), as a new string is generated to hold the result after reversal. The solution operates in-place for the reversal step.
Can the Reverse Prefix of Word problem be solved without using extra space?
Yes, the solution can be optimized to work in-place by performing the reversal directly on the original string or its representation.
How can two-pointer scanning help in solving the Reverse Prefix of Word problem?
Two-pointer scanning allows you to efficiently locate the first occurrence of the target character and reverse the required portion of the string with minimal overhead.
Need direct help with Reverse Prefix of Word instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Reverse Prefix of Word from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine the minimum swaps to balance a bracket string using two-pointer scanning with invariant tracking efficiently.
Open problem page#2019 The Score of Students Solving Math ExpressionCalculate student scores for a single-digit math expression using state transition dynamic programming to track all valid outcomes efficiently.
Open problem page#2030 Smallest K-Length Subsequence With Occurrences of a LetterFind the lexicographically smallest subsequence of length k with at least repetition occurrences of a given letter using a stack approach.
Open problem page