Reverse String

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

O(N + M), where ‘N’ denotes the length of the string ‘S’, and ‘M’ denotes the number of operations.
 

We iterate over all the operations and, in constant time, increment the corresponding operations’ value in ‘c’. We declare an array of size ‘N’ / 2 in ‘c’ and iterate over it to perform prefix sums.

Hence, the time complexity is O(N + M).

O(N), where ‘N’ denotes the length of the string ‘S’.
 

We create an array ‘c’ of size ‘N’ / 2.

Hence, the space complexity is O(N).