Home » Technical Interview Questions » String Interview Questions » Perform String Shifts Leetcode

Perform String Shifts Leetcode




String

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.

String Shifts

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.
READ  Count Negative Numbers in a Sorted Matrix LeetCode Solution

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup