In this guide, we will explore an In-Place Algorithm for modifying strings in C++ with multiple illustrations.
In this particular algorithm, the objective is to relocate all elements positioned at even indices within a specified string to the string's end. It is crucial to uphold the original sequence of both odd and even elements during this relocation process.
For example, convert a given string "a1b2c3d4e5f6g7h8i9j1k2l3m4" into "abcdefghijklm1234567891234" in situ, maintaining O(n) time complexity.
These are the steps:
Remove the largest size prefix substring of the form 3k + 1 . Finding the greatest non-negative number k such that 3k+1 is less than or equal to n (length of string) is what we do in this phase.
- Implement the cycle leader iteration technique, starting with the index 1, 3, 9, etc., to this substring. All the elements of this substring are relocated to their proper locations using the cycle leader iteration technique, which implies that all the alphabets are moved to the left half of the substring and all the digits are transferred to the right half.
- Applying the first and second stages, process the remaining substring iteratively.
- We currently simply need to combine the processed sub-strings. Start at any end (let's say the left), choose two substrings, and execute the following actions:
- Simply flip or reverse the first sub-string's second half.
- Simply invert or oppose the first half of the second sub-string.
- Just combine the first half of the second substring with the second half of the first substring to oppose or reverse them.
- Until and unless all sub-strings are linked, repeat step no. 4. It is the same as k-way merging, where the first and second substrings are linked. The outcome is combined with the third, and so forth.
Example:
Let's use an example to better understand it:
Please consider that the figures referenced in the illustration consist of 10, 11, and 12. Utilize solely these figures as individual characters for clearer comprehension.
Two segments of length 10 are generated by dividing into segments of the format 3k+1. Segments of 4 and 2 are employed to form the third and fourth segments, correspondingly.
0 1 2 3 4 5 6 7 8 9
a 1 b 2 c 3 d 4 e 5
10 11 12 13 14 15 16 17 18 19
f 6 g 7 h 8 i 9 j 10
20 21 22 23
k 11 l 12
24 25
m 13
- After implementing the cycle leader iteration algorithm with the initial sub-string:
When the subsequent substring undergoes the cycle leader iteration method:
0 1 2 3 4 5 6 7 8 9
a b c d e 1 2 3 4 5
10 11 12 13 14 15 16 17 18 19
f g h i j 6 7 8 9 10
20 21 22 23
k 11 l 12
24 25
m 13
- When the third substring undergoes the cycle leader iteration method:
When the fourth substring undergoes the cycle leader iteration technique:
0 1 2 3 4 5 6 7 8 9
a b c d e 1 2 3 4 5
10 11 12 13 14 15 16 17 18 19
f g h i j 6 7 8 9 10
20 21 22 23
k l 11 12
24 25
m 13
Combining the initial part of the second substring with the latter portion of the first substring:
- The beginning of the second substring is merged with the end of the first substring in reverse order.
0 1 2 3 4 5 6 7 8 9
a b c d e 5 4 3 2 1 <--------- First Sub-string
10 11 12 13 14 15 16 17 18 19
j i h g f 6 7 8 9 10 <--------- Second Sub-string
20 21 22 23
k l 11 12
24 25
m 13
- The reversed first half of the second substring is combined with the reversed second half of the first substring, resulting in only three substrings.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
a b c d e f g h i j 1 2 3 4 5 6 7 8 9 10
20 21 22 23
k l 11 12
24 25
m 13
Combining the first and second substrings results in the inversion of the initial half of the second substring and the latter half of the first substring.
The initial section of the subsequent string and the latter part of the preceding string, each reversed, are joined together to form two consolidated substrings.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
a b c d e f g h i j k l 1 2 3 4 5 6 7 8 9 10 11 12
24 25
m 13
Connecting the initial and subsequent substrings involves flipping the first half of the second substring and the latter half of the first substring.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
a b c d e f g h i j k l 12 11 10 9 8 7 6 5 4 3 2 1 <----- First Sub-string
24 25
m 13 <----- Second Sub-string
- The reversed first half of the second substring is concatenated with the reversed second half of the first substring to form a single, combined substring.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
a b c d e f g h i j k l m 1 2 3 4 5 6 7 8 9 10 11 12 13
The code is displayed below according to the algorithm mentioned earlier:
Example 1:
#include <bits/stdc++.h>
using namespace std;
bool isVowel(char c) {
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U');
}
void moveVowelsToBeginning(char* str) {
int left = 0;
int right = strlen(str) - 1;
while (left < right) {
while (!isVowel(str[left]) && left < right) {
left++;
}
while (isVowel(str[right]) && left < right) {
right--;
}
if (left < right) {
swap(&str[left], &str[right]);
left++;
right--;
}
}
}
int main() {
char str[] = "HelloWorld";
moveVowelsToBeginning(str);
cout << str;
return 0;
}
Output:
oellHWrldo
Example: 2
Let's consider another instance to demonstrate the In-Place algorithm for String Conversion in C++.
#include <bits/stdc++.h>
using namespace std;
void reverseWord(char* start, char* end) {
while (start < end) {
swap(*start, *end);
start++;
end--;
}
}
void reverseWordsInSentence(char* sentence) {
char* start = sentence;
char* end = sentence;
while (*end) {
end++;
if (*end == ' ' || *end == '\0') {
reverseWord(start, end - 1);
start = end + 1;
}
}
// Reverse the entire sentence to get the words in the correct order
reverseWord(sentence, end - 1);
}
int main() {
char sentence[] = "This is a sample sentence to reverse words";
reverseWordsInSentence(sentence);
cout << sentence << endl;
return 0;
}
Output:
sihT si a elpmas ecnetnes ot esrever sdrow
Important Points:
- If the array size is already in the form 3k+1 , the cycle leader iteration algorithm can be used right away. There is no requirement to join.
- Only arrays with a size of the form 3k + 1 can use the cycle leader iteration technique.
