Last Updated: 15 Apr, 2022

Reverse String

Moderate

Asked in companies

Solve now

Problem statement

You are given a string ‘S’. You are also given ‘M’ integers in an array ‘A’. You perform ‘M’ operations on this string. The operations are given in an array ‘A’ of size ‘M’.

You perform the operations in the order they appear in the array ‘A’. In the ‘i’th operation, you reverse the substring of ‘S’ from the position ‘A[i]’ to ‘len(S)’ - ‘A[i]’ - 1 (0 based).

Your task is to find the string after performing all the operations.

Example :

‘S’ = “aabcd”, ‘M’ = 2, ‘A’ = [0, 1]
After 1st operation i.e, reversing from [0, 4], ‘S’ = “dcbaa”.
After 2nd operation i.e, reversing from [1, 3], ‘S’ = “dabca”.
Hence, the answer is “dabca”.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains a string ‘S’ consisting of lowercase English characters without spaces.

The second line of each test case contains a single integer ‘M’ denoting the number of operations.

The third line of each test case contains ‘M’ space-separated integers denoting the elements of the array ‘A’.

Output Format :

For each test case, find the string after performing all the operations.

Output for each test case will be printed on a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
1 ≤ len(S) ≤ 10^5
1 ≤ M ≤ 10^5
Each ‘A[i]’ is such that the range [‘A[i]’, len(‘S’) - ‘A[i]’ - 1] is non-empty.
It is guaranteed that the sum of lengths of ‘S’ and ‘M’ is ≤ 10^5 for all test cases, respectively.

Time limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

Let ‘n’ be the length of string ‘S’. First, we need to make an important observation. An element at position ‘i’ can either remain at the position ‘i’ or position ‘n’ - ‘i’ - 1. Why?
Let’s take an example, “cdbagh”. The possible reverse operations are [0,5], [1, 4], [2, 3]. When can the letter ‘c’ (at position 0) change its place? It can only change its place after the operation [0, 5]. And it will end up at position 5. Again performing the same operation [0, 5], ‘c’ will be back at its position. So, ‘c’ can only be present at positions 0 or ‘m’ - 1.
Try similarly to find the positions ‘d’ can end up. It will only end up at positions 1 or ‘n’ - 2.
So, we can say that a character at position ‘i’ can either remain at ‘i’ or at ‘n’ - ‘i’ - 1.
The next observation is that the order of operations(reversals) does not matter.
A character at a position ‘i’ will be swapped with ‘n’ - ‘i’ - 1 only if, in all the operations, it’s reversed an odd number of times.
So, now we have the algorithm. For each position, we have to find, in how many operations, the character at this position will be swapped? Also, notice that we have to do this for only the first half of the string, as the characters in the rest half will automatically be swapped accordingly.
The next question arises, how to find the number of occurrences of each position in all the operations. Let’s understand with an example.
Suppose len(‘S’) = ‘n’ = 6, and the operations are [0, 1, 2]. We will use the sum technique. When we say an operation is 0, we mean swapping all the characters with the corresponding positions from the back of the string. So, if the string is “abcdef”, the string will become “fedcba”. For this purpose, we can maintain an array of size ‘n’ / 2 and add 1 to all the entries in the range [‘a[i]’, ‘n’ / 2). To perform this operation fast enough, as ‘m’ and ‘n’ are large, we can increment ‘c[i]’ by 1 and then take the prefix sums. Here in the array ‘c’, we store the number of occurrences.
For the above example and the operations, let ‘c’ be the array of size 3 (‘n’ = 6), [0, 0, 0].
After 1st operation, ‘c’ = [1, 0, 0].
After 2nd operation, ‘c’ = [1, 1, 0].
After 3rd operation, ‘c’ = [1, 1, 1].
Then, we take the prefix sums, ‘c’ = [1, 2, 3]. This means the character at position ‘0’ was swapped 1 time, and the character at position ‘2’ was swapped 3 times.
See the algorithm section for implementation details.

Algorithm:

Store the length of the string ‘S’ in a variable ‘n’.
Declare an array of size ‘n’ / 2, and initialize all the values of ‘c’ to ‘0’. We are taking size as ‘n’ / 2, as we only want to find the number of occurrences of characters in the first half. They will be automatically swapped for the rest half when we swap a character in the first half.
Iterate over all the operations, (let ‘a[i]’ be the current operation) and check if ‘a[i]’ < ‘n’ / 2. If it is, then perform the operation ‘c[a[i]]’ += 1. This is because, if ‘a[i]’ == ‘n’ / 2, then no effect of this operation on the string.
Then take the prefix sums in the array ‘c’. So, iterate from 1 to ‘n’ / 2 and do ‘c[i]’ += ‘c[i - 1]’.
Iterate again, from ‘i’ = 0 to ‘n’ / 2 and this time, check if ‘c[i]’ is odd or even.
If ‘c[i]’ is odd, then do swap(‘c[i]’, ‘c[n - i - 1]’).
If ‘c[i]’ is even, do nothing.
Finally, return the string ‘s’.

Solve now