Reverse Prefix of Word

Easy

Amazon

1 view

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

Amazon

1 view

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

The most straightforward approach is to iterate through the string to find the first occurrence of the target character. If found, create a substring from the beginning of the string up to and including the character, reverse it, and then concatenate it with the remaining part of the original string.

Code (Python)

def reverse_prefix_naive(word: str, ch: str) -> str:
    index = -1
    for i, c in enumerate(word):
        if c == ch:
            index = i
            break
    
    if index == -1:
        return word
    
    prefix = word[:index+1]
    reversed_prefix = prefix[::-1]
    remaining = word[index+1:]
    
    return reversed_prefix + remaining

Big O Analysis

Time Complexity: O(n), where n is the length of the word. In the worst case, we iterate through the entire string to find the character, and string slicing and concatenation also take O(n) time.
Space Complexity: O(n), because we create new strings for the reversed prefix and the remaining part of the word.

Optimal Solution

The optimal solution aims to reduce space complexity while maintaining the same time complexity.

Code (Python)

def reverse_prefix_optimal(word: str, ch: str) -> str:
    index = word.find(ch)
    if index == -1:
        return word
    
    word_list = list(word)
    left, right = 0, index
    while left < right:
        word_list[left], word_list[right] = word_list[right], word_list[left]
        left += 1
        right -= 1
    
    return "".join(word_list)

Big O Analysis

Time Complexity: O(n), where n is the length of the word. Finding the index takes O(n) in the worst case. Reversing the prefix also takes O(n/2) which simplifies to O(n).
Space Complexity: O(n) because we convert the input string into a list. This is because strings are immutable in python. If strings were mutable, the space complexity would be O(1).

Edge Cases

Character Not Found: If the character ch is not present in the string word, the function should return the original string.
Empty String: While the constraints specify a minimum length of 1, it's good to consider the case where the input string is empty. The code handles this implicitly as word.find() would return -1.
Character at the Beginning: If the character ch is at the beginning of the string word, the entire string should be reversed.
Long Strings: The code needs to handle long strings efficiently without causing memory issues, which the current solution does.

Solution

Naive Solution

Code (Python)

def reverse_prefix_naive(word: str, ch: str) -> str:
    index = -1
    for i, c in enumerate(word):
        if c == ch:
            index = i
            break
    
    if index == -1:
        return word
    
    prefix = word[:index+1]
    reversed_prefix = prefix[::-1]
    remaining = word[index+1:]
    
    return reversed_prefix + remaining

Big O Analysis

Time Complexity: O(n), where n is the length of the word. In the worst case, we iterate through the entire string to find the character, and string slicing and concatenation also take O(n) time.
Space Complexity: O(n), because we create new strings for the reversed prefix and the remaining part of the word.

Optimal Solution

The optimal solution aims to reduce space complexity while maintaining the same time complexity.

Code (Python)

def reverse_prefix_optimal(word: str, ch: str) -> str:
    index = word.find(ch)
    if index == -1:
        return word
    
    word_list = list(word)
    left, right = 0, index
    while left < right:
        word_list[left], word_list[right] = word_list[right], word_list[left]
        left += 1
        right -= 1
    
    return "".join(word_list)

Big O Analysis

Time Complexity: O(n), where n is the length of the word. Finding the index takes O(n) in the worst case. Reversing the prefix also takes O(n/2) which simplifies to O(n).
Space Complexity: O(n) because we convert the input string into a list. This is because strings are immutable in python. If strings were mutable, the space complexity would be O(1).

Edge Cases

Character Not Found: If the character ch is not present in the string word, the function should return the original string.
Empty String: While the constraints specify a minimum length of 1, it's good to consider the case where the input string is empty. The code handles this implicitly as word.find() would return -1.
Character at the Beginning: If the character ch is at the beginning of the string word, the entire string should be reversed.
Long Strings: The code needs to handle long strings efficiently without causing memory issues, which the current solution does.