Skip to main content
Talentd

Reverse String Prefix - Solution & Explanation

EasyTwo PointersString4 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 100
  • s consists 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointers SimulationO(n)O(1)Best general solution; efficient in-place reversal of the prefix
Stack-Based ReversalO(n)O(n)Useful for explaining the reversal concept step by step
Substring + Built-in ReverseO(n)O(n)Quick implementation in high-level languages with slicing support

Video Solution

Reverse String Prefix | Leetcode 3794 | Explanation With Code | Java ā€¢ codewithsitaram ā€¢ 135 views views

Watch 4 more video solutions ā†’

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).

Ready to solve this problem?

Practice Reverse String Prefix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water