Reverse Prefix of Word | LeetCode # 2000

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.

Constraints

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

Example

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".

Solution

To solve this coding problem we will

• Iterate through word and find first index of ch.
• Start a while loop with two pointers i = 0 and j = first index of ch.
• Swap characters at i and j.
• Increase i by 1 and decrease j by 1.
• Terminate loop if i >= j.

C++ implementation of above solution is as follows.

class Solution {
public:
    string reversePrefix(string word, char ch) {
       int n = word.size();
       int firstIndex = 0;

       for(int i=0; i<n; i++) {
        if(word[i] == ch) {
            firstIndex = i;
            break;
        }
       }

       int i=0;
       int j = firstIndex;

       while(i < j) {
        char temp = word[i];
        word[i] = word[j];
        word[j] = temp;
        i++;
        j--;
       }

       return word;
    }
};

Time Complexity

O(n) where n = number of characters in the word.

Space Complexity

O(1)