Modify a string by performing given shift operations

0 0 5 minutes read

Given a string S containing lowercase English alphabets, and a matrix shift[][] consisting of pairs of the form{direction, amount}, where the direction can be 0 (for left shift) or 1 (for right shift) and the amount is the number of indices by which the string S is required to be shifted. The task is to return the modified string that can be obtained after performing the given operations.

Note: A left shift by 1 refers to removing the first character of S and append it to the end. Similarly, a right shift by 1 refers to removing the last character of S and insert at the beginning.

Examples

Input: S = “abc”, shift[][] = {{0, 1}, {1, 2}}
Output: cab
Explanation:
[0, 1] refers to shifting S[0] to the left by 1. Therefore, the string S modifies from “abc” to “bca”.
[1, 2] refers to shifting S[0] to the right by 1. Therefore, the string S modifies from “bca”to “cab”.

Input: S = “abcdefg”, shift[][] = { {1, 1}, {1, 1}, {0, 2}, {1, 3} }
Output: efgabcd
Explanation:
[1, 1] refers to shifting S[0] to the right by 1. Therefore, the string S modifies from “abcdefg” to “gabcdef”.
[1, 1] refers to shifting S[0] to the right by 1. Therefore, the string S modifies from “gabcdef” to “fgabcde”.
[0, 2] refers to shifting S[0] to the left by 2. Therefore, the string S modifies from “fgabcde” to “abcdefg”.
[1, 3] refers to shifting S[0] to the right by 3. Therefore, the string S modifies from “abcdefg” to “efgabcd”.

Naive Approach: The simplest approach to solve the problem is to traverse the matrix shift[][] and shift S[0] by amount number of indices in the specified direction. After completing all shift operations, print the final string obtained.

Time Complexity: O(N²)
Auxiliary space: O(N)

Efficient Approach: To optimize the above approach, follow the steps below:

Initialize a variable, say val, to store the effective shifts.
Traverse the matrix shift[][] and perform the following operations on every i^th row:
If shift[i][0] = 0 (left shift), then decrease val by -shift[i][1].
Otherwise (left shift), increase val by shift[i][1].
Update val = val % len (for further optimizing the effective shifts).
Initialize a string, result = “”, to store the modified string.
Now, check if val > 0. If found to be true, then perform the right rotation on the string by val.
Otherwise, perform left rotation of the string by |val| amount.
Print the result.

Below is the implementation of the above approach:

C++

// C++ implementation
// of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the string obtained
// after performing given shift operations
void stringShift(string s,
                 vector<vector<int> >& shift)
{
 
    int val = 0;
 
    for (int i = 0; i < shift.size(); ++i)
 
        // If shift[i][0] = 0, then left shift
        // Otherwise, right shift
        val += shift[i][0] == 0
                   ? -shift[i][1]
                   : shift[i][1];
 
    // Stores length of the string
    int len = s.length();
 
    // Effective shift calculation
    val = val % len;
 
    // Stores modified string
    string result = "";
 
    // Right rotation
    if (val > 0)
        result = s.substr(len - val, val)
                 + s.substr(0, len - val);
 
    // Left rotation
    else
        result
            = s.substr(-val, len + val)
              + s.substr(0, -val);
 
    cout << result;
}
 
// Driver Code
int main()
{
    string s = "abc";
    vector<vector<int> > shift = {
        { 0, 1 },
        { 1, 2 }
    };
 
    stringShift(s, shift);
 
    return 0;
}

Java

// Java implementation
// of above approach
import java.io.*;
class GFG 
{
 
  // Function to find the string obtained
  // after performing given shift operations
  static void stringShift(String s, int[][] shift)
  {
    int val = 0;
    for (int i = 0; i < shift.length; ++i)
 
      // If shift[i][0] = 0, then left shift
      // Otherwise, right shift
      if (shift[i][0] == 0)
        val -= shift[i][1];
    else
      val += shift[i][1];
 
    // Stores length of the string
    int len = s.length();
 
    // Effective shift calculation
    val = val % len;
 
    // Stores modified string
    String result = "";
 
    // Right rotation
    if (val > 0)
      result = s.substring(len - val, (len - val) + val)
      + s.substring(0, len - val);
 
    // Left rotation
    else
      result = s.substring(-val, len + val)
      + s.substring(0, -val);
 
    System.out.println(result);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String s = "abc";
    int[][] shift
      = new int[][] {{ 0, 1 }, { 1, 2 }};
 
    stringShift(s, shift);
  }
}
 
// This code is contributed by Dharanendra L V

C#

// C# implementation
// of above approach
using System;
 
public class GFG 
{
 
  // Function to find the string obtained
  // after performing given shift operations
  static void stringShift(String s, int[,] shift)
  {
    int val = 0;
    for (int i = 0; i < shift.GetLength(0); ++i)
 
      // If shift[i,0] = 0, then left shift
      // Otherwise, right shift
      if (shift[i,0] == 0)
        val -= shift[i, 1];
    else
      val += shift[i, 1];
 
    // Stores length of the string
    int len = s.Length;
 
    // Effective shift calculation
    val = val % len;
 
    // Stores modified string
    String result = "";
 
    // Right rotation
    if (val > 0)
      result = s.Substring(len - val, val)
      + s.Substring(0, len - val);
 
    // Left rotation
    else
      result = s.Substring(-val, len)
      + s.Substring(0, -val);
 
    Console.WriteLine(result);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    String s = "abc";
    int[,] shift
      = new int[,] {{ 0, 1 }, { 1, 2 }};
 
    stringShift(s, shift);
  }
}
 
// This code contributed by shikhasingrajput

Python3

# Python implementation
# of above approach
 
# Function to find the string obtained
# after performing given shift operations
def stringShift(s, shift):
    val = 0
    for i in range(len(shift)):
 
        # If shift[i][0] = 0, then left shift
        # Otherwise, right shift
        val += -shift[i][1] if shift[i][0] == 0 else shift[i][1]
 
    # Stores length of the string
    Len = len(s)
 
    # Effective shift calculation
    val = val % Len
 
    # Stores modified string
    result = ""
 
    # Right rotation
    if (val > 0):
        result = s[Len - val:Len] + s[0: Len - val]
 
    # Left rotation
    else:
        result = s[-val: Len] + s[0: -val]
 
    print(result)
 
# Driver Code
s = "abc"
shift = [
    [ 0, 1 ],
    [ 1, 2 ]
]
stringShift(s, shift)
 
# This code is contributed by shinjanpatra

Javascript

<script>
 
// Javascript implementation
// of above approach
 
// Function to find the string obtained
// after performing given shift operations
function stringShift(s, shift)
{
 
    var val = 0;
 
    for (var i = 0; i < shift.length; ++i)
 
        // If shift[i][0] = 0, then left shift
        // Otherwise, right shift
        val += shift[i][0] == 0
                   ? -shift[i][1]
                   : shift[i][1];
 
    // Stores length of the string
    var len = s.length;
 
    // Effective shift calculation
    val = val % len;
 
    // Stores modified string
    var result = "";
 
    // Right rotation
    if (val > 0)
        result = s.substring(len - val,len)
                 + s.substring(0, len - val);
 
    // Left rotation
    else
        result
            = s.substring(-val, len )
              + s.substring(0, -val);
 
    document.write( result);
}
 
// Driver Code
var s = "abc";
var shift = [
    [ 0, 1 ],
    [ 1, 2 ]
];
stringShift(s, shift);
 
// This code is contributed by importantly.
</script>

Output:

cab

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!