Reverse String Prefix solution and explanation
4 more videos on this problem
Reverse String Prefix | Leetcode 3794 | Explanation With Code | Javacodewithsitaram · 5:39 · 135 views
3794. Reverse String Prefix (Leetcode Easy)Programming Live with Larry · 2:14 · 133 views
LeetCode 3794 - Reverse String Prefix | Easy String Problem Explained | Day 7 DSA ChallengeTapan Vachhani · 2:55 · 40 views
LeetCode 3794 | Reverse String Prefix | Biweekly Contest 173 SolutionTechWheel · 13:49 · 34 views
Leetcode 3794 Reverse String Prefix - Explained In HindiAlgorithmicIQ · 8:22 · 31 views
The problem
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 <= 100sconsists of lowercase English letters.1 <= k <= s.length
Approach overview
Problem 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.
Solution
We reverse the first k characters of the string according to the problem description, and then concatenate them with the remaining characters.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the string.
class Solution:
def reversePrefix(self, s: str, k: int) -> str:
return s[:k][::-1] + s[k:]class Solution {
public String reversePrefix(String s, int k) {
StringBuilder sb = new StringBuilder(s.substring(0, k));
return sb.reverse().toString() + s.substring(k);
}
}class Solution {
public:
string reversePrefix(string s, int k) {
string t = s.substr(0, k);
reverse(t.begin(), t.end());
return t + s.substr(k);
}
};function reversePrefix(s: string, k: number): string {
return s.slice(0, k).split('').reverse().join('') + s.slice(k);
}func reversePrefix(s string, k int) string {
t := []byte(s[:k])
slices.Reverse(t)
return string(t) + s[k:]
}Complexity analysis
| 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 |
Frequently asked questions
Is Reverse String Prefix easy or hard?
Reverse String Prefix is considered an Easy problem. The logic involves basic string traversal and a simple prefix reversal using two pointers. It is commonly used to test fundamental string manipulation skills.
Reverse String Prefix Python/Java solution
In Python, you can locate the character using index() and reverse the prefix with slicing like word[:i+1][::-1] + word[i+1:]. In Java, convert the string to a char array and swap characters between index 0 and the target index using two pointers.
How to solve Reverse String Prefix in O(n)?
Scan the string to find the first index of the target character. Once found, place one pointer at the start of the string and another at that index, then swap characters while moving the pointers toward each other. This reverses the prefix in linear time with constant extra space.
What is the best approach for Reverse String Prefix?
The two pointers simulation is the best approach. First locate the index of the target character, then reverse the prefix by swapping characters from both ends until the pointers meet. This solution runs in O(n) time and uses O(1) extra space, making it optimal for interviews.
Is Reverse String Prefix asked at Google/Amazon/Meta?
String manipulation problems like Reverse String Prefix frequently appear in coding interviews at companies such as Amazon, Meta, and Google. While the exact problem may vary, the core skills tested include string processing, pointer manipulation, and clean implementation of simple algorithms.
What data structure is used in Reverse String Prefix?
The optimal solution mainly uses the two pointers technique on a string or character array. Alternative implementations may use a stack to reverse the prefix, but that adds extra space. The in-place two pointer approach avoids additional data structures.
What is the time complexity of Reverse String Prefix?
The time complexity is O(n), where n is the length of the string. You perform a single scan to find the first occurrence of the character and at most another pass to reverse the prefix. Both steps are linear, so the total complexity remains O(n).