Shifting Letters II

Leetcode Problem:

• Shifting Letters II

Summary

• Given a string s and a 2D integer array shifts, shift the characters in s from the start index to the end index forward if direction is 1, or backward if direction is 0.

Approach

• This solution uses a prefix sum array to efficiently calculate the cumulative sum of shifts for each character
• It then iterates over the string, adding the prefix sum to the current character's ASCII value and taking the modulus 26 to wrap around the alphabet.

Complexity

• O(n + m) where n is the length of the string s and m is the number of shifts, as it needs to iterate over the string and the shifts array once.

Explanation

• The prefix sum array pSum is used to store the cumulative sum of shifts for each character
• For each shift, the sum of the character at the start index and the sum of the character at the end index plus the shift direction are added to pSum[start] and pSum[end+1] respectively
• Then, the string is iterated over, and the prefix sum is added to the current character's ASCII value to get the shifted character
• The modulus 26 is taken to wrap around the alphabet.

Solution Code:

class Solution {
public:
    int pSum[500001];
    int fb[2] = {25, 1};
    string shiftingLetters(string s, vector>& shifts) {
        for(int i = 0 ; i < shifts.size(); i++){
            int start = shifts[i][0];
            int end = shifts[i][1];
            int dir = shifts[i][2];
            pSum[start] += fb[dir];
            pSum[start] %= 26;
            pSum[end+1] += fb[dir ^ 1];
            pSum[end+1] %= 26;
            
        }

        string ans = "";
        for(int i = 0 ; i < s.size(); i++){
            pSum[i+1] += pSum[i];
            pSum[i] %= 26;
            unsigned char c = s[i] + pSum[i];
            if(c > 'z') c = 'a' + (c - 'z') - 1;
            if(c < 'a') c = 'z' - ('a' - c - 1);
            ans += c;
        }
        
        return ans;
    }
};