Shifting Letters LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Facebook Microsoft Oracle
Array StringViews 3065

Problem Statement

Shifting Letters says that we have given a string s and an array shifts.

Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times. We have to return the final string after all shifts are applied.

Example 1:

Input:

 s = "abc", shifts = [3,5,9]

Output:

 "rpl"

Explanation:

  • We start with “abc”.
  • After Shifting the first 1 letter of s by 3, we have “dbc”.
  • After shifting the first 2 letters of s by 5, we have “igc”.
  • After shifting the first 3 letters of s by 9, we have “rpl”.
  • Hence “rpl” is our final answer.

Example 2:

Input:

 s = "aaa", shifts = [1,2,3]

Output:

 "gfd"

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.
  • shifts.length == s.length
  • 0 <= shifts[i] <= 109

Approach

Idea

  1. We have to calculate how many times i-th character is shifted.
  2. So just calculate the number of shifts on each position, by shifts[i] += shift[i+1].
  3. We will do the task in reverse order.
  4. We have to maintain a  reverse prefix sum of the shift array and this will be equal to the number of shifts for each character.
  5. One thing we should focus if we found that our character ASCII score exceeds the value of the ASCII score of ‘z’ we should start counting from ‘a.

Code

Shifting Letters LeetCode C++ Solution

class Solution {
public:
    #define ll int
    string shiftingLetters(string s, vector<int>& shifts) {
        ll i,n=s.size();   
        for(i=n-1;i>=0;i--)
        {   if(i+1<n)
            shifts[i]+=shifts[i+1];
            shifts[i]=shifts[i]%26;
            ll ind=s[i]-'a';
            ind=ind+shifts[i];
            if(ind>25)
            { 
                ind=ind-26;
            }
              
            s[i]=char('a'+ind);
        }
       
        return s;
    }
};

Shifting Letters LeetCode Java Solution

class Solution {
    public String shiftingLetters(String s, int[] shifts) {
        int i,n=shifts.length;
        
        char[] str = s.toCharArray();

        for(i=n-1;i>=0;i--)
        {  if(i+1<n)
            shifts[i]+=shifts[i+1];
            shifts[i]=shifts[i]%26;
            int ind=s.charAt(i)-'a';
            ind=ind+shifts[i];
            if(ind>25)
            {
                ind=ind-26;
            }               
            str[i] = (char)('a'+ind);
        }

        
         return new String(str);
    }
}

Complexity Analysis of Shifting Letters LeetCode Solution:

Time Complexity

Time complexity is O(N). N is the length of the array. We are traversing the array only once.

Space Complexity

For C++ code space complexity is O(1) as we are not taking any extra space. For Java code, it is O(N) as we are making a new string.

Translate »