# Shifting Letters LeetCode Solution

Difficulty Level Medium
Array StringViews 170

## 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:

• 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 <= 10`5
• `s` consists of lowercase English letters.
• `shifts.length == s.length`
• `0 <= shifts[i] <= 10`9

## 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);
}
}
```

## 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 »