In this problem, we will perform M reverse queries on the given string according to the array values.
The naïve approach to solving the problem is to reverse each string segment according to the given array value.
The optimized approach uses the logic that when we reverse the same substring two times, we get the original string.
Problem statement − We have given an alpha string containing the alphabetical characters. Also, we have given an arr[] array of size M containing the positive integers. We need to perform the M operations on the given string and return the final string.
In each operation, we need to take the arr[i] and reveres the substring arr[i] to N − arr[i] + 1.
示例例子
输入
alpha = "pqrst"; arr = {2, 1};
输出
tqrsp
Explanation
执行第一个查询后，字符串变为 'psrqt'。
执行第二个查询后，我们得到了 'tqrsp'。
输入
− alpha = "pqrst"; arr = {1, 1};
输出
− ‘pqrst’
Explanation − 如果我们对同一个查询执行偶数次，我们会得到相同的字符串。
输入
− alpha = "pqrst"; arr = {1, 1, 1};
输出
− ‘tsrqp’
Explanation − If we perform the same query for an odd number of times, we get the reverse of the string.
Approach 1
In this approach, we will use the reverse() method to reverse the substring. We will take the starting and ending pointers using the given query and reverse the substring of the given string.
Algorithm
步骤 1 - 开始遍历查询数组。
第2步 - 使用arr[p] - 1初始化'left'变量。
Step 3 − Initialize the ‘right’ variable with str_len − arr[p] + 1.
Step 4 − Use the reverse() method to reverse the substring from left pointer to right pointer.
Example
#includeusing namespace std; void reverseStrings(string &alpha, int str_len, vector &arr, int arr_len){ // Traverse all queries for (int p = 0; p < arr_len; p++){ // Get starting pointer int left = arr[p] - 1; // Ending pointer int right = str_len - arr[p] + 1; // Reverse the string reverse(alpha.begin() + left, alpha.begin() + right); } } int main(){ int str_len = 5; string alpha = "pqrst"; int arr_len = 2; vector arr = {2, 1}; reverseStrings(alpha, str_len, arr, arr_len); cout << "The string after performing queries is " << alpha << endl; return 0; }
输出
The string after performing queries is tqrsp
Time complexity − O(N*M) for reversing substring M times.
Space complexity − O(1) as we don’t use any dynamic space.
方法二
In this approach, we will calculate that particular index and how many times included in the reversal using given queries. If any index is included for an even number of times, we don’t need to reverse it. If any index is included for an odd number of times in all given queries, we need to reverse the character at particular indexes.
Algorithm
步骤 1 - 初始化长度等于字符串长度的 'cnt' 列表，用 0 存储特定索引在反转中出现的次数。
Step 2 − Traverse the array of given queries, and take a left and right pointer of the string according to the current query.
Step 3 − Also execute the changeRange() function to update the ‘cnt’ list according to the current query's left and right pointers.
Step 3.1 − In the changeRange() function, increment the value at the ‘left’ index in the ‘cnt’ list.
第3.2步 - 减小“cnt”列表中位于“right + 1”指针右侧的所有值。
Here, we needed to increment all the values of the ‘cnt’ list by 1 in the range [left, right]. So, we incremented only cnt[left] by 1 because taking the prefix sum will increment all values by 1, which is at right to the ‘left’ index. Also, we don’t want to increment the cnt values between [right, str_len] indexes, so we have decremented it by 1 already as the prefix sum will increase it by 1.
Step 4 − Next, execute the getPrefixSum() function to calculate the prefix sum of the ‘cnt’ list.
Step 4.1 − In the getPrefixSum() function, traverse the string and add the previous element’s value to the current element.
步骤 5 - 接下来，以逆序遍历‘cnt’列表。如果当前元素是奇数，则将其追加到‘tmp’字符串中。
步骤 6 - 用0初始化‘p’和‘q’，按照原始顺序遍历‘cnt’列表。
步骤 7 − 如果‘cnt’列表中的当前元素是奇数，则使用tmp[q]更新alpha[p]。
Step 8 − At the end, return the alpha string.
Example
的中文翻译为：示例
#include#include using namespace std; void changeRange(vector & cnt, int left, int right) { // Increase the value of the left index cnt[left]++; // Decrement value for all indexes after the right index if (right + 1 < cnt.size()) cnt[right + 1]--; } void getPrefixSum(vector & cnt) { // Calculate prefix sum for (int p = 1; p < cnt.size(); p++) { cnt[p] += cnt[p - 1]; } } string reverseStrings(string alpha, int str_len, vector & arr, int arr_len) { vector cnt(str_len, 0); // Traverse the array for (int p = 0; p < arr_len; p++) { int left = arr[p] <= (str_len + 1) / 2 ? arr[p] - 1 : str_len - arr[p]; int right = arr[p] <= (str_len + 1) / 2 ? str_len - arr[p] : arr[p] - 1; // Changes index ranges between left and right changeRange(cnt, left, right); } getPrefixSum(cnt); string tmp; // Store characters with the odd reversal in the reverse order in the tmp string for (int p = cnt.size() - 1; p >= 0; p--) { if (cnt[p] % 2 != 0) tmp.push_back(alpha[p]); } int p = 0, q = 0; // For even reversal, pick the character from the original string. // For odd reversal, pick the character from the temp string. for (p = 0; p < cnt.size(); p++) { if (cnt[p] % 2 != 0) alpha[p] = tmp[q++]; } // Answer string return alpha; } int main() { int str_len = 5; string alpha = "pqrst"; int arr_len = 2; vector arr = { 2, 1 }; alpha = reverseStrings(alpha, str_len, arr, arr_len); cout << "The string after performing queries is: " < 输出
The string after performing queries is: tqrspTime complexity − O(M*N + N), where O(M*N) is to update the ‘cnt’ list according to the query, and O(N) is to update the given string.
空间复杂度 - 使用 'cnt' 列表为 O(N)。
在第一种方法中，我们使用了reveres()方法来执行给定字符串上的所有查询。在第二种方法中，我们使用了前缀和技术来计算特定索引在反转中出现的次数。
