[Solved] Shifting Letters II LeetCode Contest

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0.

Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').

Return the final string after all such shifts to s are applied.

Shifting Letters II LeetCode Contest

Example 1:

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
Output: "ace"
Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac".
Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd".
Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".

Example 2:

Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]
Output: "catz"
Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz".
Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".

Constraints:

• 1 <= s.length, shifts.length <= 5 * 104
• shifts[i].length == 3
• 0 <= starti <= endi < s.length
• 0 <= directioni <= 1
• s consists of lowercase English letters.

Solution

string shiftingLetters(string s, vector<vector<int>>& shifts) {
    int line[50001] = {};
    for (auto &shift : shifts) {
        line[shift[0]] += shift[2] ? 1 : -1;
        line[shift[1] + 1] += shift[2] ? -1 : 1;
    }
    for (int i = 0, val = 0; i < s.size(); ++i) {
        val = (val + line[i]) % 26;
        s[i] = 'a' + (26 + (s[i] - 'a') + val) % 26;
    }
    return s;
}

 public String shiftingLetters(String s, int[][] shifts) {
        char[] ch = s.toCharArray();
        int[] count = new int[s.length()+1];
        
        for(int[] shift : shifts){
            int value = shift[2] == 1 ? 1 : -1;
            count[shift[0]] += value;
            count[shift[1] + 1] -= value;
        }
        
        int sum = 0;
        for(int i = 0; i < count.length - 1; i++){
            sum += count[i];
            int newChar = ((ch[i] - 'a') + sum) % 26;
            if(newChar < 0) newChar+= 26;
            ch[i] =  (char)('a' + newChar);
        }
        
        return String.valueOf(ch);
    }

class Solution:
	def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
		toshift = [0]*(len(s) +1)
		
		#marking start and end points only for start and end points of each shift 
		for i in shifts:
			if i[2] == 1:
				toshift[i[0]] += 1
				toshift[i[1]+1] -= 1
			else:
				toshift[i[0]] -= 1
				toshift[i[1]+1] += 1
				
		for j in range(1, len(s)):                  #calculating prefixSum
				toshift[j] += toshift[j-1]
				
		l = list(s)                                 #converting in list for doing modification
		for i in range(len(l)):
			if toshift[i]>0:                        #for forward
				acc= ord(l[i]) + (toshift[i]%26)    #doing modulo by 26 because we have 26 alphabets and if suppose we to shift alphabet by 43 ie(43 % 26 = 1) so we will shift by 1 
				if (acc) > 122:
					acc = 96 + (acc-122)            #if range exceeds then first subtract by 122 then add it in 96 (if still you did'nt get intution of it try doing dry run of it on some test cases)
					
			else:                                   #for backward
				acc= ord(l[i]) - (abs(toshift[i])%26)
				if (acc) < 97:
					acc = 123 - (97 - acc)
					
			l[i] = chr(acc)                         #finally updating that character

		return(''.join(l))

Happy Learning – If you require any further information, feel free to contact me.