Reverse Prefix of Word

Easy

Google

Topics:

StringsTwo Pointers

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd".

Return the resulting string.

Example 1:

Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Explanation: 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"
Explanation: 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"
Explanation: "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.

Reverse Prefix of Word

Easy

Google

Topics:

StringsTwo Pointers

For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd".

Return the resulting string.

Example 1:

Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Explanation: 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"
Explanation: 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"
Explanation: "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

Naive Solution

A brute force solution would involve iterating through the string to find the index of the character ch. If found, reverse the substring from index 0 to that index (inclusive). If not found, return the original string.

Code (Python)

def reverse_prefix_brute_force(word: str, ch: str) -> str:
    index = -1
    for i in range(len(word)):
        if word[i] == ch:
            index = i
            break

    if index == -1:
        return word

    reversed_substring = word[:index+1][::-1]
    return reversed_substring + word[index+1:]

Time Complexity

O(N) in the worst case, where N is the length of the string word. This is because we iterate through the string once to find the character ch and then potentially reverse a portion of the string, which also takes O(N) time.

Space Complexity

O(N). In the worst case, we create a new reversed substring of length N.

Optimal Solution

The optimal solution is essentially the same as the brute force one, but can be written more concisely. The core logic remains the same:

Find the index of the first occurence of ch.
If ch isn't found, return the original string.
Otherwise, reverse the prefix of the string up to and including the index of ch.

Code (Python)

def reverse_prefix_optimal(word: str, ch: str) -> str:
    try:
        index = word.index(ch)
        return word[:index+1][::-1] + word[index+1:]
    except ValueError:
        return word

Time Complexity

O(N), where N is the length of the string word. The word.index(ch) operation takes O(N) time in the worst case. The string slicing and reversal also contribute O(N) operations.

Space Complexity

O(N). String slicing creates a copy of the string or a portion of it.

Edge Cases

Empty string: The problem statement specifies that the word length is between 1 and 250, so we don't need to handle empty strings.
Character not found: The code handles this case by returning the original string.
Character at the beginning: If ch is the first character, the entire string up to that point (just the first character) is reversed (which results in the same string).
Character at the end: If ch is the last character, the entire string is reversed.

Solution

Naive Solution

Code (Python)

def reverse_prefix_brute_force(word: str, ch: str) -> str:
    index = -1
    for i in range(len(word)):
        if word[i] == ch:
            index = i
            break

    if index == -1:
        return word

    reversed_substring = word[:index+1][::-1]
    return reversed_substring + word[index+1:]

Time Complexity

Space Complexity

O(N). In the worst case, we create a new reversed substring of length N.

Optimal Solution

The optimal solution is essentially the same as the brute force one, but can be written more concisely. The core logic remains the same:

Find the index of the first occurence of ch.
If ch isn't found, return the original string.
Otherwise, reverse the prefix of the string up to and including the index of ch.

Code (Python)

def reverse_prefix_optimal(word: str, ch: str) -> str:
    try:
        index = word.index(ch)
        return word[:index+1][::-1] + word[index+1:]
    except ValueError:
        return word

Time Complexity

O(N), where N is the length of the string word. The word.index(ch) operation takes O(N) time in the worst case. The string slicing and reversal also contribute O(N) operations.

Space Complexity

O(N). String slicing creates a copy of the string or a portion of it.

Edge Cases

Empty string: The problem statement specifies that the word length is between 1 and 250, so we don't need to handle empty strings.
Character not found: The code handles this case by returning the original string.
Character at the beginning: If ch is the first character, the entire string up to that point (just the first character) is reversed (which results in the same string).
Character at the end: If ch is the last character, the entire string is reversed.