Perform String Shifts Leetcode

A shift is a process in which alphabets are incremented by 1 in their ASCII value. For the last alphabet z it starts again i.e. shift of z will be a. In perform string shifts leetcode problem we have Given a string s (lowercase characters only) and an array a[ ] of size equal to the length of a string containing a number of shifts to perform on the string. For each a[i] apply a[i] number of shifts on all the characters in string till i’th position.

Explanation

Let the string s = “abc” and the given array a[ ] = {1, 4, 7}

• Step 1 : Current character = ‘a’, shift value = 1. Therefore s = “bbc”.
• Step 2 : Current character = ‘b’, previous character = ‘a’, shift value = 4. Therefore s = “ffc”.
• Step 3 : Current character = ‘c’, previous characters = ‘a’ and ‘b’, shift value = 7. Therefore s = “mmj”.

Therefore, Output : mmj

Example

Input :

s = “abc”

a = { 1, 4, 7}

Output : mmj

Input :

s = “string”

a = {4, 1, 2, 7, 1, 3}

Output : khetrj

Algorithm to Perform String Shifts Leetcode

1. Initialize a string variable and an array a[ ] of type integer of the same size.
2. Iterate through the given array a[ ] from the second last element to the starting element and update the value at current index in given array a[ ] as the addition of the value at current index in given array a[ ] and the value at current index+1 i.e. the next index in given array a[ ]. After that, update the value at the current index in given array a[ ] as the result of the mod of the value at the current index in given array a[ ] with 26.
3. Similarly, traverse again and update the character at current index in given string s as the result of ( ( (s[i] – ‘a’) + a[i]) % 26 + ‘a’).
4. Return the updated string variable.

C++ Program to Perform String Shifts Leetcode

#include <bits/stdc++.h>
using namespace std;

string shift(string s, int a[], int n){

    for(int i=n-2; i>=0; i--){
        a[i] += a[i + 1];
        a[i] %= 26;
    }
    
    for(int i=0; i<n; i++) {
        s[i] = (((s[i] - 'a') + a[i]) % 26 + 'a');
    }
    
    return s;
}

int main(){
    string s = "string";
    int a[] = {4, 1, 2, 7, 1, 3};
    int n = sizeof(a)/sizeof(a[0]);
    cout<<shift(s, a, n);
    return 0;
}

khetrj

Java Program to Perform String Shifts Leetcode

class shiftString {
    
    public String shift(String s, int[] a){
         
        int prev = 0;
        for(int i=a.length-1; i>=0; i--){            
            a[i] = (a[i] + prev) % 26;
            prev = a[i];
        }
         
        char[] chars = s.toCharArray();
        for(int i=0; i<chars.length; i++){
            chars[i] = (char)('a' + (((int)chars[i] + a[i]) % 'a') % 26);
        }
        return String.valueOf(chars);
    }
    
    public static void main(String[] args) {        
        shiftString str = new shiftString();
        String s = "string";
        int[] a = new int[] {4, 1, 2, 7, 1, 3};
        System.out.print(str.shift(s, a));
    }
}

khetrj

Complexity Analysis to Perform String Shifts Leetcode

Time Complexity: O(n) where n is the size of the given array a[ ].

Auxiliary Space: O(1) because we used constant space.

References