Shift all prefixes by given lengths

0 0 5 minutes read

Given a string S containing letters and digits, and an integer array Shift where, $1 \leq S.length()=length(Shift) \leq 10^{5}$ and for each element of Shift array $0 \leq Shift[i] \leq 10^{9}$ . The task is, for each Shift[i] = X, you have to shift the first i+1 letters of S, X times. Return the final string after all applying all such shift to S.
Note: Shift means cyclically increment ASCII value.

Examples:

Input: S = “abc789”, Shift = [2, 5, 9]
Output: “qpl706”
Explanation: Starting with “abc”.
After shifting the first 1 letters of S by 2, we have “cbc”.
After shifting the first 2 letters of S by 5, we have “hgc”.
After shifting the first 3 letters of S by 9, we have “qpl”.
Input : S = “zambiatek”, Shift[] = [ 11, 10000, 9999999 ]
Output : qdnyulaufkuug

Approach: The i-th character of S is shifted Shift[i] + Shift[i+1] + … + Shift[Shift.length – 1] times.
So we update the Shift array backward to know the exact number of shifts to be applied to each element of string S.
Now,

Traverse the given text (S) one character at a time.
For each character, transform the given character as per the rule, i:e apply shift, Shift[i] times.
Return the new string generated.

Below is the implementation of the above approach:

C++

// CPP implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find S after shifting each letter
string shift_S(string S, int Shift[], int n)
{
    // update shift array for each element
    for (int i = n - 2; i >= 0; --i)
        Shift[i] += Shift[i + 1];
 
    // finding the new shifted string
    string result = "";
 
    // traverse S and shift letters according to shift array
    for (int i = 0; i < S.length(); i++) {
 
        // For upper letters
        if (isupper(S[i])) {
            result += char((int(S[i]) + Shift[i] - 'A') % 26 + 'A');
        }
 
        // For lower letters
        else if (islower(S[i])) {            
            result += char((int(S[i]) + Shift[i] - 'a') % 26 + 'a');
        }
 
        // For digits
        else {            
            result += char((int(S[i]) + Shift[i] - '0') % 10 + '0');
        }
    }
 
    // Return the shifted string
    return result;
}
 
// Driver program
int main()
{
    string S = "abc";
    int Shift[] = { 2, 5, 9 };
 
    int n = sizeof(Shift) / sizeof(Shift[0]);
 
    // function call to print required answer
    cout << shift_S(S, Shift, n);
 
    return 0;
}
 
// This code is written by Sanjit_Prasad

Java

// Java implementation of the above approach 
 
public class GfG{
         
    // Function to find S after shifting each letter 
    public static String shift_S(String S, int Shift[], int n) 
    { 
        // update shift array for each element 
        for (int i = n - 2; i >= 0; --i) 
            Shift[i] += Shift[i + 1]; 
       
        // finding the new shifted string 
        String result = ""; 
       
        // traverse S and shift letters according to shift array 
        for (int i = 0; i < S.length(); i++) { 
       
            // For upper letters 
            if (Character.isUpperCase(S.charAt(i))) { 
                result += (char)(((int)(S.charAt(i)) + Shift[i] - 'A') % 26 + 'A'); 
            } 
       
            // For lower letters 
            else if (Character.isLowerCase(S.charAt(i))) {             
                result += (char)(((int)(S.charAt(i)) + Shift[i] - 'a') % 26 + 'a'); 
            } 
       
            // For digits 
            else {             
                result += (char)(((int)(S.charAt(i)) + Shift[i] - '0') % 10 + '0'); 
            } 
        } 
       
        // Return the shifted string 
        return result; 
    } 
 
     public static void main(String []args){
         
        String S = "abc"; 
        int Shift[] = { 2, 5, 9 }; 
        int n = Shift.length;
         
        // Function call to print the required answer 
        System.out.println(shift_S(S, Shift, n));
     }
}
   
// This code is contributed by Rituraj Jain

Python3

# Python3 implementation of above approach
 
# Function to find S after shifting
# each letter
def shift_S(S, Shift, n):
     
    # update shift array for 
    # each element
    for i in range(n - 2, -1, -1):
        Shift[i] = Shift[i] + Shift[i + 1]
     
    # finding the new shifted string
    result = ""
     
    # traverse S and shift letters
    # according to shift array
    for i in range(len(S)):
         
        # For upper letters
        if(S[i].isupper()):
            result = result + chr((ord(S[i]) + Shift[i] -
                                   ord('A')) % 26 + ord('A'))
             
        # For lower letters
        elif (S[i].islower()):
            result = result + chr((ord(S[i]) + Shift[i] -
                                   ord('a')) % 26 + ord('a'))
         
        # For digits
        else:
            result = result + chr((ord(S[i]) + Shift[i] -
                                   ord('0')) % 10 + ord('0'))
         
    # Return the shifted string
    return result 
 
# Driver Code
S = "abc"
Shift = [2, 5, 9]
n = len(Shift)
 
# Function call to print the required answer
print(shift_S(S, Shift, n))
 
# This code is contributed 
# by Shashank_Sharma

C#

// C# implementation of the above approach 
using System;
 
class GfG{ 
         
// Function to find S after 
// shifting each letter 
public static String shift_S(string S, 
                             int[] Shift,
                             int n) 
{ 
     
    // Update shift array for each element 
    for(int i = n - 2; i >= 0; --i) 
        Shift[i] += Shift[i + 1]; 
     
    // Finding the new shifted string 
    string result = ""; 
     
    // Traverse S and shift letters 
    // according to shift array 
    for(int i = 0; i < S.Length; i++) 
    { 
         
        // For upper letters 
        if (Char.IsUpper(S[i])) 
        { 
            result += (char)(((int)(S[i]) + 
                     Shift[i] - 'A') % 26 + 'A'); 
        } 
     
        // For lower letters 
        else if (Char.IsLower(S[i]))
        {             
            result += (char)(((int)(S[i]) + 
                     Shift[i] - 'a') % 26 + 'a'); 
        } 
     
        // For digits 
        else
        {             
            result += (char)(((int)(S[i]) + 
                     Shift[i] - '0') % 10 + '0'); 
        } 
    } 
     
    // Return the shifted string 
    return result; 
} 
 
// Driver code
public static void Main()
{ 
    string S = "abc"; 
    int[] Shift = { 2, 5, 9 }; 
    int n = Shift.Length; 
     
    // Function call to print 
    // the required answer 
    Console.WriteLine(shift_S(S, Shift, n)); 
} 
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript implementation of above approach
 
// Function to find S after shifting
// each letter
function shift_S(S, Shift, n){
     
    // update shift array for
    // each element
    for(let i = n - 2;i>=0;i--){
        Shift[i] = Shift[i] + Shift[i + 1]
    }
     
    // finding the new shifted string
    let result = ""
     
    // traverse S and shift letters
    // according to shift array
    for(let i=0;i<S.length;i++){
         
        // For upper letters
        if(S.charCodeAt(i) >= 65 && S.charCodeAt(i) <= 90)
            result = result + String.fromCharCode((S.charCodeAt(i) + Shift[i] -'A'.charCodeAt(0)) % 26 + 'A'.charCodeAt(0))
             
        // For lower letters
        else if (S.charCodeAt(i) >= 97 && S.charCodeAt(i) <= 122)
            result = result + String.fromCharCode((S.charCodeAt(i) + Shift[i] -'a'.charCodeAt(0)) % 26 + 'a'.charCodeAt(0))
         
        // For digits
        else
            result = result + String.fromCharCode((S.charCodeAt(i) + Shift[i] -'0'.charCodeAt(0)) % 26 + '0'.charCodeAt(0))
    }
         
    // Return the shifted string
    return result
}
 
// Driver Code
let S = "abc"
let Shift = [2, 5, 9]
let n = Shift.length
 
// Function call to print the required answer
document.write(shift_S(S, Shift, n))
 
// This code is contributed
// by Shinjanpatra
 
</script>

Output:

qpl

Time Complexity: O(N), where N is the length of string S.
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!