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 characterch
in the stringword
. Thefind()
method returns the index of 'ch' if it is found, and-1
. The syntaxword.find(ch)
executes this search. -
Check Character Presence: We then check if
ch
is present inword
by examining if the result fromfind()
is not-1
. Ifch
isn't present (i.e., iffind()
returns-1
), we do nothing and return the originalword
unmodified. -
Reverse String Segment: If
ch
is found, we proceed to reverse the segment ofword
from the start to the index wherech
is found. Python strings support slicing, which we use to reverse a substring. The slice operationword[i::-1]
is used, wherei
is the index returned by thefind()
operation. This operation reverses the string from the start up to indexi
. -
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 ofword
. -
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:
1class Solution:
2 def reversePrefix(self, word: str, ch: str) -> str:
3 i = word.find(ch)
4 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 EvaluatorExample 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"
andch = "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 isO(n)
wheren
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)
wherek
is the index of the found character (orn
in the worst case if the character is at the end of the string). While string slicing is typicallyO(n)
in Python, in this case we are considering the slice operation up to the first occurrence ofch
. Therefore, the cost is relative to the position ofch
. -
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.
Which technique can we use to find the middle of a linked list?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first