Watch 9 video solutions for Reverse String Prefix, a easy level problem involving Two Pointers, String. This walkthrough by Programming Live with Larry has 115 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s and an integer k.
Reverse the first k characters of s and return the resulting string.
Example 1:
Input: s = "abcd", k = 2
Output: "bacd"
Explanation:
The first k = 2 characters "ab" are reversed to "ba". The final resulting string is "bacd".
Example 2:
Input: s = "xyz", k = 3
Output: "zyx"
Explanation:
The first k = 3 characters "xyz" are reversed to "zyx". The final resulting string is "zyx".
Example 3:
Input: s = "hey", k = 1
Output: "hey"
Explanation:
The first k = 1 character "h" remains unchanged on reversal. The final resulting string is "hey".
Constraints:
1 <= s.length <= 100s consists of lowercase English letters.1 <= k <= s.lengthProblem Overview: You are given a string and a target character. Locate the first occurrence of that character and reverse the substring from the beginning of the string up to that position. The rest of the string stays unchanged. If the character does not exist in the string, return the original string.
Approach 1: Simulation with Two Pointers (O(n) time, O(1) space)
This problem fits naturally with the two pointers technique. First scan the string to find the index of the target character. Once found, place one pointer at the start of the string and another at that index. Swap characters while moving the left pointer forward and the right pointer backward until they meet. Only the prefix is modified, so the remainder of the string remains untouched. The scan plus reversal both take linear time, giving O(n) time complexity with O(1) extra space when the string is modified in place.
Approach 2: Stack-Based Reversal (O(n) time, O(n) space)
A straightforward simulation uses a stack to reverse the prefix. Iterate through the string and push characters onto a stack until the target character is encountered. When you reach the character, pop elements from the stack to rebuild the reversed prefix. Then append the remaining characters of the original string. This approach mirrors the conceptual reversal process but uses extra memory proportional to the prefix length, resulting in O(n) time and O(n) auxiliary space.
Approach 3: Built-in Reverse / Slicing (O(n) time, O(n) space)
Many languages provide convenient substring and reverse operations. After finding the index of the target character, extract the prefix using substring or slicing, reverse it using a built-in function, and concatenate it with the remainder of the string. The algorithm still requires scanning the string once to locate the character, so the runtime remains O(n). Because most languages allocate a new string during slicing or reversing, the space complexity becomes O(n).
Recommended for interviews: The two pointers simulation is the expected solution. It demonstrates control over in-place string manipulation and understanding of the two pointers pattern. Showing a stack or slicing approach first can illustrate the basic idea, but interviewers typically look for the in-place reversal because it achieves O(1) extra space while keeping the implementation simple.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers Simulation | O(n) | O(1) | Best general solution; efficient in-place reversal of the prefix |
| Stack-Based Reversal | O(n) | O(n) | Useful for explaining the reversal concept step by step |
| Substring + Built-in Reverse | O(n) | O(n) | Quick implementation in high-level languages with slicing support |