LeetCode Problem 3794

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

LeetCode 3794 - Reverse String Prefix

Problem Understanding

This problem gives us a string s and an integer k. Our task is to reverse only the first k characters of the string while leaving the remaining characters unchanged.

In other words, we take the substring consisting of the first k characters, reverse its order, and then append the rest of the original string after it.

For example, if s = "abcd" and k = 2, the first two characters are "ab". Reversing them produces "ba". The remaining portion of the string is "cd", so the final result becomes "bacd".

The input consists of:

• A string s
• An integer k

The output is a new string formed after reversing the prefix of length k.

The constraints are very small:

• 1 <= s.length <= 100
• 1 <= k <= s.length

These constraints tell us that performance is not a concern. Even solutions that create multiple temporary strings will run comfortably within limits. The problem is primarily about correctly manipulating string slices.

Some important observations and edge cases include:

• When k = 1, reversing a single character does not change anything.
• When k = s.length, the entire string is reversed.
• The problem guarantees that k is always valid, so we never need to handle out-of-range values.
• The string length can be as small as one character, in which case the answer is identical to the input.

Approaches

Brute Force Approach

A straightforward solution is to manually reverse the first k characters one character at a time.

We could iterate backward through the prefix, build a new string containing the reversed prefix, then append the remaining portion of the original string. This approach is easy to understand and produces the correct answer because every character in the prefix is copied in reverse order while the suffix remains unchanged.

Although this approach is perfectly acceptable for the given constraints, repeatedly concatenating strings can be inefficient in some languages because strings are immutable. Each concatenation may create a new string.

Optimal Approach

The key observation is that we only need two pieces:

1. The first k characters.
2. The remaining characters.

Most languages provide efficient slicing operations. We can extract the prefix, reverse it directly, and concatenate it with the untouched suffix.

This keeps the implementation concise and easy to verify.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k + n)	O(n)	Manually builds reversed prefix character by character
Optimal	O(n)	O(n)	Reverse sliced prefix and append remaining suffix

Since k <= n, both approaches effectively run in linear time. The slicing-based solution is simpler and cleaner.

Algorithm Walkthrough

1. Extract the first k characters of the string.

This is the portion that must be reversed. 2. Reverse the extracted prefix.

Reversing changes the order of the first k characters while preserving all characters. 3. Extract the remaining suffix beginning at index k.

These characters should remain exactly as they appear in the original string. 4. Concatenate the reversed prefix and the unchanged suffix.

This produces the final transformed string. 5. Return the resulting string.

Why it works

The problem only requires modifying the first k characters. By isolating that prefix, reversing it, and then attaching the untouched remainder of the string, we exactly reproduce the required output. Every character in positions 0 through k - 1 appears in reverse order, while every character from position k onward remains unchanged.

Python Solution

class Solution:
    def reversePrefix(self, s: str, k: int) -> str:
        return s[:k][::-1] + s[k:]

The implementation directly follows the algorithm.

First, s[:k] extracts the prefix that must be reversed. The slice operation [::-1] reverses that prefix. Finally, s[k:] extracts the unchanged suffix, and the two parts are concatenated together.

Because Python strings are immutable, a new string is created and returned as the result.

Go Solution

func reversePrefix(s string, k int) string {
    prefix := []byte(s[:k])

    left, right := 0, len(prefix)-1
    for left < right {
        prefix[left], prefix[right] = prefix[right], prefix[left]
        left++
        right--
    }

    return string(prefix) + s[k:]
}

The Go solution converts the prefix into a byte slice so that individual characters can be swapped in place.

A standard two pointer reversal is performed:

• One pointer starts at the beginning.
• One pointer starts at the end.
• Characters are swapped until the pointers meet.

After reversal, the byte slice is converted back into a string and concatenated with the unchanged suffix.

Unlike Python, Go strings are immutable, so converting to a mutable byte slice is the simplest way to perform the reversal.

Worked Examples

Example 1

Input: s = "abcd", k = 2

Step-by-Step Trace

Step	Value
Original string	"abcd"
Prefix s[:2]	"ab"
Reversed prefix	"ba"
Suffix s[2:]	"cd"
Final result	"bacd"

Output: "bacd"

Example 2

Input: s = "xyz", k = 3

Step-by-Step Trace

Step	Value
Original string	"xyz"
Prefix s[:3]	"xyz"
Reversed prefix	"zyx"
Suffix s[3:]	""
Final result	"zyx"

Output: "zyx"

Example 3

Input: s = "hey", k = 1

Step-by-Step Trace

Step	Value
Original string	"hey"
Prefix s[:1]	"h"
Reversed prefix	"h"
Suffix s[1:]	"ey"
Final result	"hey"

Output: "hey"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Reversing the prefix and constructing the result touches at most all characters once
Space	O(n)	A new string containing the result is created

The dominant cost comes from building the resulting string. Since strings are immutable in both Python and Go, creating the answer requires space proportional to the length of the string.

Test Cases

sol = Solution()

assert sol.reversePrefix("abcd", 2) == "bacd"      # Example 1
assert sol.reversePrefix("xyz", 3) == "zyx"        # Example 2
assert sol.reversePrefix("hey", 1) == "hey"        # Example 3

assert sol.reversePrefix("a", 1) == "a"            # Single character string
assert sol.reversePrefix("abcde", 5) == "edcba"    # Entire string reversed
assert sol.reversePrefix("abcde", 2) == "bacde"    # Small prefix reversal
assert sol.reversePrefix("aaaaa", 3) == "aaaaa"    # All characters identical
assert sol.reversePrefix("leetcode", 4) == "teelcode"  # General case
assert sol.reversePrefix("ab", 1) == "ab"          # Small string, k = 1
assert sol.reversePrefix("ab", 2) == "ba"          # Small string, k = length

Test Summary

Test	Why
"abcd", 2	Basic prefix reversal
"xyz", 3	Entire string reversed
"hey", 1	Single character prefix
"a", 1	Minimum input size
"abcde", 5	Boundary case where k = n
"abcde", 2	Typical partial reversal
"aaaaa", 3	Repeated characters
"leetcode", 4	General nontrivial example
"ab", 1	Small string with minimal prefix
"ab", 2	Small string with complete reversal

Edge Cases

Edge Case 1: k = 1

When the prefix contains only one character, reversing it produces exactly the same character. A buggy implementation might perform unnecessary operations or incorrectly modify the string.

For example:

s = "hello"
k = 1

The reversed prefix remains "h", so the answer is still "hello". The implementation handles this naturally because reversing a one-character slice has no effect.

Edge Case 2: k = s.length

When k equals the length of the string, the entire string must be reversed.

For example:

s = "abcd"
k = 4

The prefix becomes "abcd", which reverses to "dcba", and the suffix is empty. The algorithm correctly returns "dcba".

Edge Case 3: Single Character String

The smallest valid input contains only one character.

For example:

s = "a"
k = 1

Both the prefix and the entire string consist of the same single character. The algorithm returns "a" without any special handling.

Edge Case 4: Repeated Characters

When multiple characters are identical, it may be difficult to visually verify correctness.

For example:

s = "aaaaa"
k = 3

The reversed prefix is still "aaa", so the resulting string remains "aaaaa". The algorithm still performs the correct transformation even though the output appears unchanged.