2000. Reverse Prefix of Word

Problem Description

The task here involves manipulating a given string word based on the presence of a specified character ch. We are required to find the first occurrence of the character ch within word. Once found, we reverse the substring of word that starts from the beginning (index 0) and ends at the position where ch is found (this position is included in the segment to be reversed). In case the character ch does not exist in word, no changes should be made to the original string. The main objective is to return the modified string as a result. The problem stresses that the input string word is 0-indexed, which means the first character is at position 0.

For example, consider word = "abcdefd" and ch = "d". Since the first occurrence of "d" is at index 3, we reverse the substring from index 0 to 3, resulting in "dcbaefd" which is the output.

Intuition

The intuition behind the solution is to first locate the index of the character ch within the string word using a string search function. In Python, this is typically done using the find() method, which returns the lowest index of the substring if it is found, or -1 if it is not found. If the character ch isn't found, i will be -1 and the solution will simply return the original string as no action is needed.

If the character is found, we need to reverse the segment of the string up to and including that character. In Python, this can be efficiently accomplished using slicing. The slice word[i::-1] produces a new string that consists of the characters from the start of word up to i, reversed. After reversing the desired segment, we concatenate it with the remaining part of word that comes after the character ch (word[i + 1 :]) to form the final string.

The approach is direct and utilizes Python's powerful slicing capabilities, enabling the operation to be performed in a single line of code and with clear readability.

Learn more about Two Pointers patterns.

Solution Approach

The solution approach for this problem leverages a straightforward algorithm, which goes as follows:

Find the Character 'ch': Firstly, we use the find() method available in Python to search for the first occurrence of the character ch in the string word. The find() method returns the index of 'ch' if it is found, and -1. The syntax word.find(ch) executes this search.
Check Character Presence: We then check if ch is present in word by examining if the result from find() is not -1. If ch isn't present (i.e., if find() returns -1), we do nothing and return the original word unmodified.
Reverse String Segment: If ch is found, we proceed to reverse the segment of word from the start to the index where ch is found. Python strings support slicing, which we use to reverse a substring. The slice operation word[i::-1] is used, where i is the index returned by the find() operation. This operation reverses the string from the start up to index i.
Concatenate the Segments: The last step is to concatenate the reversed segment with the rest of the string that follows after 'ch'. This is done using word[i + 1 :], which gives us the substring from the character immediately after 'ch' to the end of word.
Return the Result: The final step is to combine the two substrings— the reversed segment and the remaining part of the original string— to form the modified string and return it as the result.

The overall solution is efficient, requiring only a single pass to find the character and another pass to create the reversed segment. It does not use any additional data structures, and the operations used (string search, slicing, and concatenation) are all native to Python and designed for performance. The provided code encapsulates this logic concisely:

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 :]

This implementation highlights the effectiveness of Python's string manipulation features, allowing for an elegant expression of the solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach:

Consider the word to be "example" and the ch to be "p". The task is to find the first occurrence of the character "p" in the word "example" and reverse the string from the start up to and including the character "p".

Find the Character 'ch': We start by finding the index of "p" using word.find(ch). In our example, word = "example" and ch = "p". The character "p" is at index 4 in "example".
Check Character Presence: We check if "p" is found in "example". Since the find() method returned 4, we know "p" is present (it didn't return -1).
Reverse String Segment: We then reverse the string segment from the start to index 4, which includes "p". Using Python slicing, we write this operation as word[4::-1], which gives us "elpmaxe".
Concatenate the Segments: Now we concatenate the reversed segment with the rest of the string after "p". The remaining part of the string is obtained with word[5:], which is "le". So, appending it to the reversed segment, we get "elpmaxe" + "le" = "elpmaxele".
Return the Result: Finally, the modified string "elpmaxele" is returned, representing the string "example" with the segment up to and including the first occurrence of "p" reversed.

By following these steps, we used the given solution approach on the word "example" with the target character "p", resulting in "elpmaxele".

Solution Implementation

1class Solution:
2    # Function to reverse the prefix of a word up to a certain character
3    def reversePrefix(self, word: str, ch: str) -> str:
4        # Find the index of the character ch in the word
5        index_of_char = word.find(ch)
6      
7        # If ch is not found, the index will be -1 and the original word is returned
8        if index_of_char == -1:
9            return word
10          
11        # If ch is found, reverse the substring from start to the index of ch (inclusive)
12        # then concatenate with the remaining substring starting from the element right after ch's index
13        # The [::-1] slice reverses the substring
14        reversed_prefix = word[:index_of_char+1][::-1]
15        remaining_word = word[index_of_char+1:]
16      
17        return reversed_prefix + remaining_word
18

1class Solution {
2    public String reversePrefix(String word, char ch) {
3        // Find the index of the first occurrence of the character 'ch' in the 'word'
4        int index = word.indexOf(ch);
5      
6        // If 'ch' is not found, return the original 'word'
7        if (index == -1) {
8            return word;
9        }
10      
11        // Convert the string into a char array for in-place reversal
12        char[] charArray = word.toCharArray();
13      
14        // Reverse the prefix of the word up to the index of 'ch'
15        for (int i = 0; i < index; ++i, --index) {
16            // Swap characters at position i and index
17            char temp = charArray[i];
18            charArray[i] = charArray[index];
19            charArray[index] = temp;
20        }
21      
22        // Convert the char array back to a string and return
23        return String.valueOf(charArray);
24    }
25}
26

1#include <algorithm> // Required for std::reverse
2#include <string>    // Required for std::string
3
4class Solution {
5public:
6    // This function takes a string and a character.
7    // It reverses the order of characters in the string up to (and including) the first occurrence of the char.
8    // Input: a string 'word' and a character 'ch'
9    // Output: the modified string with the prefix reversed, if the character is found.
10    string reversePrefix(string word, char ch) {
11        // Find the first occurrence of the character 'ch' in 'word'.
12        int index = word.find(ch);
13      
14        // If the character is found (i.e., find() doesn't return string::npos), reverse the substring.
15        if (index != string::npos) {
16            // Reverse from the beginning of 'word' to the character 'ch' (inclusive).
17            reverse(word.begin(), word.begin() + index + 1);
18        }
19      
20        // Return the modified string.
21        return word;
22    }
23};
24

1// Reverses the prefix of a given word up to and including the first occurrence of a specified character.
2// @param {string} word - The original string to be processed.
3// @param {string} ch - The character to search for in the string.
4// @return {string} - The string with the prefix reversed up to and including the first occurrence of the character.
5function reversePrefix(word: string, ch: string): string {
6    // Find the index of the character in the string.
7    const index = word.indexOf(ch) + 1;
8  
9    // If the character is not found, return the original word.
10    if (index === 0) {
11        return word;
12    }
13
14    // Slice the word up to and including the found character, reverse this part,
15    // and then join it back with the rest of the original word.
16    return [...word.slice(0, index)].reverse().join('') + word.slice(index);
17}
18

Time and Space Complexity

Time Complexity

The main operation in the given piece of code is finding the first occurrence of the character ch within the string word and then reversing the prefix up to that character.

The time complexity for the string find operation is O(n) where n is the length of the string, since in the worst case, it needs to scan the entire string.
Slicing the string to reverse the prefix takes O(k) where k is the index of the found character (or n in the worst case if the character is at the end of the string). While string slicing is typically O(n) in Python, in this case we are considering the slice operation up to the first occurrence of ch. Therefore, the cost is relative to the position of ch.
Concatenating the reversed prefix with the rest of the string is also an O(n) operation because it creates a new string from the two substrings.

Since these operations are done sequentially and we're interested in the worst-case scenario, the overall time complexity is dominated by the O(n) operations, making the total time complexity of the solution O(n).

Space Complexity

The space complexity of the code is primarily dependent on the storage needed for the output, which is the reversed prefix concatenated with the rest of the string.

Since the reversed prefix is derived from slicing the existing string, it creates a new string object with the maximum length of n.
Concatenating the reversed prefix with the rest of the string generates another new string, but since strings are immutable in Python, this is 'destructive' concatenation and also takes up to n space.

However, it is important to note that the space used for the output does not count towards the extra space usage, as it is considered the space required to hold the input and output of the function. No additional data structures are used that scale with the size of the input, therefore, the extra space complexity is O(1) (constant space for the index i and temporary substrings during the execution).

In summary, the space complexity for additional space required is O(1), while the overall space complexity (including space for inputs and outputs) is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know