[Solved] Reverse String Contest Problem

Reverse String: 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”.

Reverse String Contest Problem

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

Sample Input 1 :

2
gaagbd
3
2 2 2
dbgd
5
1 1 1 0 0

Sample Output 1 :

gagabd
dgbd

Explanation For Sample Input 1 :

For test case 1:
Here, len(‘S’) = 6. So, we need to reverse the string ‘S’[2, 3] three times.
After 1st reversal: ‘S’ = “gagabd”.
After 2nd reversal: ‘S’ = “gaagbd”.
After 3rd reversal: ‘S’ = “gagabd”.
Hence, the answer is “gagabd”.

For test case 2:
Here, len(‘S’) = 4. We need to reverse the string ‘S’[1, 2], ‘S’[1, 2], ‘S’[1, 2], ‘S’[0, 3], ‘S’[0, 3].
After 1st reversal: ‘S’ = “dgbd”
After 2nd reversal: ‘S’ = “dbgd”
After 3rd reversal: ‘S’ = “dgbd”
After 4th reversal: ‘S’ = “dbgd”
After 5th reversal: ‘S’ = “dgbd”
Hence, the answer is “dgbd”.

Sample Input 2 :

2
cgagbga
4
0 2 1 0
daa
3
1 0 1

Sample Output 2 :

cgagbga
aad

Solution

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

Time Complexity

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

Space Complexity

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

/*
    Time Complexity: O(N + M)
    Space Complexity: O(N)

    where 'N' denotes the length of the string 'S',
    and 'M' denotes the number of elements in the array.
*/


string reverseString(string s, int m, vector<int> &a) {

    // 'n' stores the length of the string 's'.
    int n = s.length();

    // 'c' stores the number of occurrences of each position in the first half.
    vector<int> c(n / 2);

    // Iterate over all the operations.
    for (int i = 0; i < m; ++i) {

        // If the operations is in the first half.
        if (a[i] < n / 2) {

            // Increment the corresponding array index by 1.
            c[a[i]]++;
        }
    }

    // Take the prefix sums of the array 'c'.
    for (int i = 1; i < n / 2; ++i) {
        c[i] += c[i - 1];
    }

    // Iterate over the array 'c'.
    for (int i = 0; i < n / 2; ++i) {

        // If 'c[i]' is odd.
        if (c[i] % 2) {

            // Swap the characters at positions 'i' and 'n' - 'i' - 1.
            swap(s[i], s[n - i - 1]);
        }
    }

    // Return the final string 's'.
    return s;
}

/*
    Time Complexity: O(N + M)
    Space Complexity: O(N)

    where 'N' denotes the length of the string 'S',
    and 'M' denotes the number of elements in the array.
*/

import java.util.ArrayList;
import java.lang.StringBuilder;
import java.lang.String;

public class Solution {
    static String reverseString(String s, int m, ArrayList<Integer> a) {    

        // 'n' stores the length of the string 's'.
        int n = s.length();
        StringBuilder str = new StringBuilder();

        str.append(s);

        // 'c' stores the number of occurrences of each position in the first half.
        ArrayList<Integer> c = new ArrayList<Integer>();

        for(int i = 0; i < n / 2; ++i) {
            c.add(0);
        }

        // Iterate over all the operations.
        for (int val : a) {

            // If the operations is in the first half.
            if (val < n / 2) {

                // Increment the corresponding array index by 1.
                c.set(val, c.get(val) + 1);
            }
        }

        // Take the prefix sums of the array 'c'.
        for (int i = 1; i < n / 2; ++i) {
            int val = c.get(i) + c.get(i - 1);
            c.set(i, val);
        }

        // Iterate over the array 'c'.
        for (int i = 0; i < n / 2; ++i) {
            // If 'c[i]' is odd.
            if ((c.get(i) & 1) == 1) {

                // Swap the characters at positions 'i' and 'n' - 'i' - 1.
                char tmp = str.charAt(i);

                str.setCharAt(i, str.charAt(n - i - 1));
                
                str.setCharAt(n - i - 1, tmp);
            }
        }

        s = str.toString();

        // Return the final string 's'.
        return s;
    }
}

'''
	Time Complexity: O(N + M)
	Space Complexity: O(N)

	where 'N' denotes the length of the string 'S',
	and 'M' denotes the number of elements in the array.
'''

from typing import *

def reverseString(s: str, m: int, a: List[int]) -> str:

	# 'n' stores the length of the string 's'.
	n = len(s)
	s = list(s)
	# 'c' stores the number of occurrences of each position in the first half.
	c = [0] * (n//2)

	# Iterate over all the operations.
	for i in range(m) :

		# If the operations is in the first half.
		if (a[i] < (n // 2)) :

			# Increment the corresponding array index by 1.
			c[a[i]] += 1
		
	

	# Take the prefix sums of the array 'c'.
	for i in range(1, n//2) :
		c[i] += c[i - 1]
	

	# Iterate over the array 'c'.
	for i in range(n//2) :

		# If 'c[i]' is odd.
		if (c[i] % 2) :

			# Swap the characters at positions 'i' and 'n' - 'i' - 1.
			s[i], s[n - i - 1] = s[n - i - 1], s[i]

	# Return the final string 's'.
	return "".join(s)

string reverseString(string s, int m, vector<int> &a) {
    // Write your code here.
        for (int i = 0; i < m; i++) {
        int start = a[i];
        int end = s.length() - a[i] - 1;
        reverse(s.begin() + start, s.begin() + end + 1);
    }
    return s;
}

import java.util.*;
public class Solution {
    static String reverseString(String s, int m, ArrayList<Integer> a) {
        // Write your code here
                int n = s.length();
        while (m > 0) {
            int i = a.get(m - 1);
            int j = n - i - 1;
            String temp = s.substring(i, j + 1);
            s = s.substring(0, i) + new StringBuilder(temp).reverse().toString() + s.substring(j + 1);
            m--;
        }
        return s;
    }
}

Happy Learning – If you require any further information, feel free to contact me.