LeetCode 2000 - Reverse Prefix of Word

The problem gives us a string word and a character ch. We must locate the first occurrence of ch inside the string. Once we find it, we reverse the substring starting at index 0 and ending at that occurrence, inclusive.

leetcodeeasytwo-pointersstringstack

LeetCode Problem 2000

Difficulty: 🟢 Easy
Topics: Two Pointers, String, Stack

Solution

Problem Understanding

The problem gives us a string word and a character ch. We must locate the first occurrence of ch inside the string. Once we find it, we reverse the substring starting at index 0 and ending at that occurrence, inclusive.

After reversing that prefix, the remainder of the string stays exactly the same.

For example, if:

word = "abcdefd"
ch = "d"

the first occurrence of "d" is at index 3. The prefix from index 0 through 3 is:

"abcd"

Reversing it gives:

"dcba"

The rest of the string is:

"efd"

Combining them produces:

"dcbaefd"

If the character ch does not appear anywhere in the string, we simply return the original string unchanged.

The constraints are very small:

  • 1 <= word.length <= 250
  • only lowercase English letters are used

Because the input size is tiny, almost any reasonable string-processing solution will run efficiently. However, the goal is still to design a clean and correct algorithm.

Several edge cases are important:

  • ch may not exist in the string at all
  • ch may appear at index 0, meaning the reversed prefix has length 1, so the string stays unchanged
  • ch may appear multiple times, but only the first occurrence matters
  • the entire string may need to be reversed if the first occurrence is at the last index

Approaches

Brute Force Approach

A brute-force solution could repeatedly build candidate prefixes while scanning the string character by character. Once the target character is found, we could manually reverse the prefix using another loop, then concatenate the remaining suffix.

For example:

  1. Scan through the string to find the first occurrence of ch
  2. Copy all characters before and including that position into a temporary array
  3. Reverse that temporary array manually
  4. Append the unchanged remainder of the string

This works because it directly follows the problem statement. However, it involves extra manual copying and reversal logic that makes the implementation more verbose than necessary.

Although the constraints are small enough that this approach is perfectly acceptable, we can simplify the solution significantly.

Optimal Approach

The key observation is that we only need to reverse a single prefix of the string. Modern programming languages already provide efficient substring and reversal operations.

The optimal strategy is:

  1. Find the index of the first occurrence of ch
  2. If it does not exist, return the original string
  3. Reverse the substring from 0 through that index
  4. Append the untouched suffix

This approach is simple, readable, and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Manually copies and reverses characters
Optimal O(n) O(n) Uses direct prefix reversal and concatenation

Algorithm Walkthrough

Optimal Algorithm

  1. Search for the first occurrence of ch in word.

We need the first matching position because the problem explicitly says to reverse only up to the first occurrence. Once we know this index, we know exactly which prefix to reverse. 2. If the character is not found, return the original string.

In this situation, no operation should be performed. Returning early avoids unnecessary work. 3. Extract the prefix from index 0 through the found index.

If the first occurrence is at index i, then the prefix is:

word[:i+1]
  1. Reverse the extracted prefix.

Reversing can be done efficiently using slicing in Python or a byte swap loop in Go. 5. Extract the suffix after the found index.

This portion of the string remains unchanged. 6. Concatenate the reversed prefix and the suffix.

The resulting string is the required answer.

Why it works

The algorithm works because it exactly matches the operation described in the problem statement. The only modification allowed is reversing the prefix ending at the first occurrence of ch. By locating that index and reversing precisely that section while leaving the remainder untouched, we guarantee the correct output.

Python Solution

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        index = word.find(ch)

        if index == -1:
            return word

        reversed_prefix = word[:index + 1][::-1]
        suffix = word[index + 1:]

        return reversed_prefix + suffix

The implementation starts by locating the first occurrence of ch using Python's built-in find() method. If find() returns -1, the character does not exist, so the original string is returned immediately.

If the character exists, the code extracts the prefix ending at that index. Python slicing with [::-1] reverses the substring efficiently and concisely.

The suffix after the target index is then extracted unchanged. Finally, the reversed prefix and suffix are concatenated to produce the final result.

The implementation closely mirrors the algorithm steps, which makes the code easy to verify and maintain.

Go Solution

func reversePrefix(word string, ch byte) string {
    index := -1

    for i := 0; i < len(word); i++ {
        if word[i] == ch {
            index = i
            break
        }
    }

    if index == -1 {
        return word
    }

    bytes := []byte(word)

    left := 0
    right := index

    for left < right {
        bytes[left], bytes[right] = bytes[right], bytes[left]
        left++
        right--
    }

    return string(bytes)
}

The Go solution follows the same logic as the Python version but uses explicit byte manipulation because Go strings are immutable.

After locating the first occurrence of ch, the string is converted into a byte slice so characters can be swapped in place. Two pointers, left and right, move toward each other while swapping characters. This efficiently reverses the prefix directly inside the byte slice.

Finally, the modified byte slice is converted back into a string and returned.

Since the input contains only lowercase English letters, treating the string as bytes is completely safe.

Worked Examples

Example 1

Input:
word = "abcdefd"
ch = "d"

The first occurrence of "d" is at index 3.

Step Value
Original string "abcdefd"
Prefix "abcd"
Reversed prefix "dcba"
Remaining suffix "efd"
Final result "dcbaefd"

Result:

"dcbaefd"

Example 2

Input:
word = "xyxzxe"
ch = "z"

The first occurrence of "z" is at index 3.

Step Value
Original string "xyxzxe"
Prefix "xyxz"
Reversed prefix "zxyx"
Remaining suffix "xe"
Final result "zxyxxe"

Result:

"zxyxxe"

Example 3

Input:
word = "abcd"
ch = "z"

The character "z" does not exist.

Step Value
Search result Not found
Operation performed None
Final result "abcd"

Result:

"abcd"

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the string once and may reverse up to all characters
Space O(n) A new string or byte slice is created during reversal

The running time is linear because every character is processed at most a constant number of times. The space complexity is linear because strings are immutable in Python and Go, so additional storage is needed for the modified result.

Test Cases

solution = Solution()

assert solution.reversePrefix("abcdefd", "d") == "dcbaefd"  # standard middle reversal
assert solution.reversePrefix("xyxzxe", "z") == "zxyxxe"    # reverse longer prefix
assert solution.reversePrefix("abcd", "z") == "abcd"        # character not present

assert solution.reversePrefix("a", "a") == "a"              # single-character string
assert solution.reversePrefix("abc", "a") == "abc"          # target at beginning
assert solution.reversePrefix("abc", "c") == "cba"          # reverse entire string

assert solution.reversePrefix("aaaaa", "a") == "aaaaa"      # repeated characters
assert solution.reversePrefix("racecar", "e") == "ecarcar"  # palindrome-like input

assert solution.reversePrefix("leetcode", "t") == "teelcode"  # reversal in middle
assert solution.reversePrefix("zzzzz", "z") == "zzzzz"        # all identical chars
Test Why
"abcdefd", "d" Basic example with middle reversal
"xyxzxe", "z" Confirms first occurrence handling
"abcd", "z" Character absent case
"a", "a" Minimum input size
"abc", "a" Prefix length is 1
"abc", "c" Entire string reversed
"aaaaa", "a" Multiple identical characters
"racecar", "e" Non-trivial middle reversal
"leetcode", "t" General mixed-character case
"zzzzz", "z" Uniform string input

Edge Cases

Character Does Not Exist

A common source of bugs is forgetting to handle the case where ch never appears in the string. If the implementation blindly attempts to reverse a prefix using an invalid index, it may produce incorrect results or runtime errors.

The solution handles this safely by checking whether the search result is -1. If so, it immediately returns the original string unchanged.

Character Appears at Index 0

If the first occurrence of ch is already at the beginning of the string, the prefix length is only one character. Reversing a single character should not change the string.

For example:

word = "abc"
ch = "a"

The implementation correctly extracts "a", reverses it to "a", and appends the unchanged suffix "bc".

Entire String Must Be Reversed

If the first occurrence of ch is at the final index, the entire string becomes the prefix.

For example:

word = "abc"
ch = "c"

The algorithm reverses the whole string and produces "cba".

The implementation handles this naturally because the suffix after the target index is simply an empty string.