#2000

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Reverse Prefix of Word

Reverse the prefix of a string starting from index 0 to the first occurrence of a given character.

Problem Statement

Given a string 'word' and a character 'ch', reverse the segment of 'word' that starts from index 0 and ends at the index of the first occurrence of 'ch'. If 'ch' does not exist in 'word', the string remains unchanged.

Return the resulting string after performing the above reversal operation.

Examples

Example 1

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

Output: "dcbaefd"

The first occurrence of "d" is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".

Example 2

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

Output: "zxyxxe"

The first and only occurrence of "z" is at index 3. Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".

Example 3

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

Output: "abcd"

"z" does not exist in word. You should not do any reverse operation, the resulting string is "abcd".

Constraints

1 <= word.length <= 250
word consists of lowercase English letters.
ch is a lowercase English letter.

Solution Approach

Two-pointer scanning

Use two pointers to locate the first occurrence of the character 'ch' and reverse the portion of the string from the start to that index. This approach ensures optimal traversal of the string.

In-place reversal

Once the target index is found, reverse the substring in place using the two-pointer technique, which eliminates the need for extra space and ensures efficient time complexity.

Handle missing character case

If the character 'ch' is not found, simply return the string unchanged. The algorithm should handle this case without performing any unnecessary operations.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because we scan the string once to locate the first occurrence of 'ch' and potentially reverse part of the string. The space complexity is O(n) due to the space required for the result string.

What Interviewers Usually Probe

Candidate can quickly identify the problem's two-pointer scanning approach.
Candidate efficiently handles cases where the target character does not exist in the string.
Candidate implements the in-place reversal technique without using unnecessary extra space.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where the target character does not exist in the string.
Not reversing the string in place, leading to extra space usage.
Overcomplicating the solution by using additional data structures instead of two-pointer scanning.

Follow-up variants

Consider handling multiple occurrences of the target character and reversing up to the last occurrence.
Extend the problem by allowing the user to reverse the segment up to a specified index instead of just the first occurrence.
Consider reversing substrings from any starting index to a given character index.

FAQ

What is the time complexity of the Reverse Prefix of Word problem?

The time complexity is O(n), where n is the length of the string 'word'. This is because we scan the string once to locate the target character and reverse the necessary part of the string.

How do you handle the case when the character does not exist in the string?

If the target character is not found in the string, the function returns the string unchanged, without performing any reversal.

What is the space complexity of this solution?

The space complexity is O(n), as a new string is generated to hold the result after reversal. The solution operates in-place for the reversal step.

Can the Reverse Prefix of Word problem be solved without using extra space?

Yes, the solution can be optimized to work in-place by performing the reversal directly on the original string or its representation.

How can two-pointer scanning help in solving the Reverse Prefix of Word problem?

Two-pointer scanning allows you to efficiently locate the first occurrence of the target character and reverse the required portion of the string with minimal overhead.

terminal

Solution

Solution 1: Simulation

First, we find the index $i$ where the character $ch$ first appears. Then, we reverse the characters from index $0$ to index $i$ (including index $i$). Finally, we concatenate the reversed string with the string starting from index $i + 1$.

1

2

3

4

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        i = word.find(ch)
        return word if i == -1 else word[i::-1] + word[i + 1 :]

Continue Practicing

#1963 minimum number of swaps to make the string balanced #2019 the score of students solving math expression #2030 smallest k length subsequence with occurrences of a letter