Sponsored
Sponsored
The brute force approach involves scanning the string to find the index of the first occurrence of the character and then reversing the substring from the start to that index. If the character is not found, the string remains unchanged. This approach makes use of two operations: the indexOf operation which finds the index of the first occurrence of the character and a reversing operation for the substring.
The time complexity is O(n) due to the search and reversal operations. The space complexity is O(n) for the storage of the resulting string.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5char* reversePrefix(char* word, char ch) {
6 int n = strlen(word);
7 int i;
8 for (i = 0; i < n; i++) {
9 if (word[i] == ch) {
10 break;
11 }
12 }
13 if (i == n) return word; // character ch not found
14
15 char* result = (char*)malloc((n + 1) * sizeof(char));
16 strncpy(result, word, n + 1);
17
18 // Reverse operation
19 for (int j = 0; j <= i; j++) {
20 result[j] = word[i - j];
21 }
22 return result;
23}
24
25int main() {
26 char word[] = "abcdxefd";
27 char ch = 'd';
28 char* result = reversePrefix(word, ch);
29 printf("%s\n", result);
30 return 0;
31}In this C solution, we first calculate the length of the string. We traverse the string to find the index of the first occurrence of the specified character. If found, we perform a reversal of the substring from start to the found index. The reversed substring is then copied back to a new result string.
The two-pointers approach is an efficient way to handle the reversed segment directly without using extra space for substring operations. This method entails finding the index of the character first and then reversing the required part of the string in place (where applicable), by gradually swapping elements from both ends of the segment moving inwards.
The time complexity remains O(n) for the search and in-place reversal. The space complexity is O(1) since no extra space proportional to input size is used.
1#include <string>
using namespace std;
string reversePrefix(string word, char ch) {
int idx = word.find(ch);
if (idx == string::npos) return word;
int left = 0, right = idx;
while (left < right) {
swap(word[left], word[right]);
left++;
right--;
}
return word;
}
int main() {
string word = "abcdxefd";
char ch = 'd';
cout << reversePrefix(word, ch) << endl;
return 0;
}The C++ solution uses two pointers to reverse the substring in place. We find the character's index, and swap characters from both ends of the prefix using a loop.