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(N2)
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 ith 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 operationsvoid 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 Codeint main(){ string s = "abc"; vector<vector<int> > shift = { { 0, 1 }, { 1, 2 } }; stringShift(s, shift); return 0;} |
Java
// Java implementation// of above approachimport 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 approachusing 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 operationsdef 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 Codes = "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 operationsfunction 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 Codevar s = "abc";var shift = [ [ 0, 1 ], [ 1, 2 ]];stringShift(s, shift);// This code is contributed by importantly.</script> |
cab
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
