We have a string S of lowercase letters, and an integer array shifts.
Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a'). 
For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.
Now for each shifts[i] = x, we want to shift the first i+1 letters of S, x times.
Return the final string after all such shifts to S are applied.
Example 1:
Input: S = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 
We start with "abc".
After shifting the first 1 letters 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", the answer.

Note:

1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        

Solutions:
class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		tot = sum(shifts)
		ans = []
		for i in range(len(S)):
			ans.append(chr((ord(S[i]) - ord('a') + tot) % 26 + ord('a')))
			tot -= shifts[i]
		return ''.join(ans)


class Solution:
	CODE_Z = ord('z')

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		ret = ''
		self.calc_shift_times(shifts)
		for x in range(len(S)):
			ret += self.shift(S[x], shifts[x])
		return ret

	@classmethod
	def shift(cls, c, shift_times):
		ret = ord(c) + shift_times % 26
		if ret > cls.CODE_Z:
			ret -= 26
		return chr(ret)

	@staticmethod
	def calc_shift_times(shifts: List[int]):
		for x in range(-2, -(len(shifts) + 1), -1):
			shifts[x] += shifts[x + 1]


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		l = len(shifts)
		s = list(S)[:l]
		a = ord('a')
		for i in range(1, len(shifts)):
			shifts[l - 1 - i] += shifts[l - i]
		print(shifts)
		for i in range(len(shifts)):
			s[i] = chr((ord(s[i]) - a + shifts[i]) % 26 + a)
		return ''.join(s)


class Solution:

	@staticmethod
	def shiftChar(c, shift):
		shift = shift % 26
		nc = ord(c)
		pos = nc - ord('a')
		if 25 - pos < shift:
			shift = -(26 - shift)
		return chr(nc + shift)

	def shiftingLetters(self, S: str, shifts) -> str:
		for i in range(len(shifts) - 2, -1, -1):
			shifts[i] += shifts[i + 1]
		return ''.join([Solution.shiftChar(c, shift) for (c, shift) in zip(S, shifts)])


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		add = 0
		arr = list(S)
		i = len(S) - 1
		while i >= 0:
			add += shifts[i]
			arr[i] = chr((ord(arr[i]) - 97 + add) % 26 + 97)
			i -= 1
		return ''.join(arr)


import string

class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		if len(S) == 0:
			return ''
		letters = string.ascii_lowercase
		num_letters = len(letters)
		final_shifts = [shift % num_letters for shift in shifts]
		running_shift = 0
		for (i, shift) in enumerate(final_shifts[::-1]):
			index = len(final_shifts) - 1 - i
			if index < len(final_shifts) - 1:
				final_shifts[index] = (final_shifts[index] + running_shift) % num_letters
			running_shift += shift
		result = []
		for (i, shift) in enumerate(final_shifts):
			letter = S[i]
			position = (letters.index(letter) + shift) % num_letters
			shift_letter = letters[position]
			result.append(shift_letter)
		return ''.join(result)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		n = len(shifts)
		A = [0] * n

		def shifting(ch, k):
			return chr((ord(ch) - 97 + k) % 26 + 97)
		A[-1] = shifts[-1]
		for i in range(n - 2, -1, -1):
			A[i] = A[i + 1] + shifts[i]
		return ''.join([shifting(c, A[i]) for (i, c) in enumerate(list(S))])


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		cnt = 0
		acc_shifts = []
		for n in shifts[::-1]:
			cnt += n
			acc_shifts.append(cnt)
		acc_shifts = acc_shifts[::-1]
		new_s = []
		a_asc = ord('a')
		z_asc = ord('z')
		for (i, n) in enumerate(acc_shifts):
			new_ascii = ord(S[i]) + n
			new_ascii = a_asc + (new_ascii - a_asc) % 26
			new_s.append(chr(new_ascii))
		return ''.join(new_s)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:

		def shift(s, n):
			curr = ord(s) - 97
			curr = 97 + (curr + n) % 26
			return chr(curr)
		S = list(S)
		shifts = shifts[::-1]
		for i in range(1, len(shifts)):
			shifts[i] += shifts[i - 1]
		shifts = shifts[::-1]
		for i in range(len(shifts)):
			S[i] = shift(S[i], shifts[i])
		return ''.join(S)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		a = ''
		cumshift = 0
		for pos in range(len(S) - 1, -1, -1):
			sh = shifts[pos] % 26
			cumshift += sh
			cumshift = cumshift % 26
			ch = S[pos]
			chn = shift(ch, cumshift)
			a = chn + a
		return a
zval = 122
aval = 97

def shift(ch, offset):
	offset = offset % 26
	och = ord(ch)
	nch = och + offset
	if nch > zval:
		nch = aval + (nch - zval - 1)
	return chr(nch)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		S_lst = list(S)
		plus = 0
		for i in range(len(shifts) - 1, -1, -1):
			plus += shifts[i]
			temp = ord(S_lst[i]) + plus % 26
			if temp > 122:
				temp = temp % 123 + 97
			S_lst[i] = chr(temp)
		return ''.join(S_lst)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		ln = len(shifts)
		new = [sum(shifts)]
		i = 0
		while i < ln - 1:
			new.append(new[-1] - shifts[i])
			i += 1
		S = list(S)
		ans = ''
		for (i, shift) in enumerate(new):
			S[i] = chr((ord(S[i]) - ord('a') + shift) % 26 + ord('a'))
		return ''.join(S)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		a = ''
		cumshift = 0
		for pos in range(len(S) - 1, -1, -1):
			cumshift = (cumshift + shifts[pos]) % 26
			ch = S[pos]
			chn = shift(S[pos], cumshift)
			a = chn + a
		return a

def shift(ch, offset):
	nch = ord(ch) + offset
	if nch > ord('z'):
		nch = ord('a') + (nch - ord('z') - 1)
	return chr(nch)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		ans = []
		X = sum(shifts) % 26
		for (i, c) in enumerate(S):
			index = ord(c) - ord('a')
			ans.append(chr(ord('a') + (index + X) % 26))
			X = (X - shifts[i]) % 26
		return ''.join(ans)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		n = len(shifts)
		ss = [0] * n
		ss[-1] = shifts[-1] % 26
		for i in range(n - 2, -1, -1):
			ss[i] = (shifts[i] + ss[i + 1]) % 26
		final_chars = [None] * n
		for (i, ch) in enumerate(S):
			_ord = ord(ch) + ss[i]
			if _ord > 122:
				_ord -= 26
			final_chars[i] = chr(_ord)
		return ''.join(final_chars)


from collections import deque

class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		offset = ord('a')
		wrap = 26
		current_shift = 0
		result = deque()
		for (c, shift) in reversed(list(zip(S, shifts))):
			current_shift = (current_shift + shift) % wrap
			after = chr(offset + (ord(c) + current_shift - offset) % wrap)
			result.append(after)
		return ''.join(reversed(result))


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		back_sum = [0] * len(shifts)
		N = 26
		back_sum = 0
		new_str = ''
		for i in range(len(S) - 1, -1, -1):
			back_sum += shifts[i]
			new_str += chr((ord(S[i]) - ord('a') + back_sum) % N + ord('a'))
		return new_str[::-1]


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		(s, ans) = ([0], [])
		for n in reversed(shifts):
			s.append((s[-1] + n) % 26)
		s = reversed(s[1:])
		for (i, c) in enumerate(S):
			n = chr((ord(c) - ord('a') + next(s)) % 26 + ord('a'))
			print(n)
			ans.append(n)
		return ''.join(ans)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		S_lst = list(S)
		plus = 0
		for i in range(len(shifts) - 1, -1, -1):
			plus += shifts[i]
			temp = ord(S_lst[i]) + plus % 26
			if temp > ord('z'):
				temp = temp % (ord('z') + 1) + ord('a')
			S_lst[i] = chr(temp)
		return ''.join(S_lst)


def shift_char(char, num):
	idx = ord(char) - ord('a')
	idx = idx + num
	idx %= 26
	return chr(ord('a') + idx)

class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		res = list(S)
		for i in range(len(shifts) - 2, -1, -1):
			shifts[i] += shifts[i + 1]
		for i in range(len(S)):
			res[i] = shift_char(res[i], shifts[i])
		return ''.join(res)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		nextS = shifts[0] % 26
		for i in range(len(S)):
			(curr, nextS) = (nextS, shifts[i + 1] % 26 if i < len(S) - 1 else 0)
			shifts[0] += curr if i > 0 else 0
			if i < len(S) - 1:
				shifts[i + 1] = -curr
		for i in range(len(S)):
			shifts[i] += shifts[i - 1] if i > 0 else 0
		return ''.join([chr((ord(c) - 97 + s) % 26 + 97) for (c, s) in zip(S, shifts)])


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		suffix_sum_shifts = []
		suffix_sum = 0
		for shift in shifts[::-1]:
			suffix_sum += shift
			suffix_sum %= 26
			suffix_sum_shifts.append(suffix_sum)
		suffix_sum_shifts = suffix_sum_shifts[::-1]
		shifted_str = ''
		for i in range(len(S)):
			new_ord = (ord(S[i]) - ord('a') + suffix_sum_shifts[i]) % 26 + ord('a')
			shifted_str += chr(new_ord)
		return shifted_str


import string

class Solution:

	def shiftingLetters(self, S, shifts):
		start = ord('a')
		res = []
		for i in reversed(range(len(shifts) - 1)):
			shifts[i] += shifts[i + 1]
		for i in range(len(S)):
			shifted = chr((ord(S[i]) - start + shifts[i]) % 26 + start)
			res.append(shifted)
		return ''.join(res)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		N = len(S)
		cumsum = [0] * N
		cumsum[-1] = shifts[-1] % 26
		for i in range(N - 2, -1, -1):
			cumsum[i] = (cumsum[i + 1] + shifts[i]) % 26
		res = []
		for i in range(N):
			c = S[i]
			res.append(chr((ord(c) - ord('a') + cumsum[i]) % 26 + ord('a')))
		return ''.join(res)


import string

class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		letters = string.ascii_lowercase
		letter_to_idx = dict()
		for (i, l) in enumerate(letters):
			letter_to_idx[l] = i
		suffix = [sum(shifts)]
		for i in range(1, len(shifts)):
			suffix.append(suffix[-1] - shifts[i - 1])
		res = ''
		for (i, c) in enumerate(S):
			res += letters[(letter_to_idx[c] + suffix[i]) % 26]
		return res


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		char = 'abcdefghijklmnopqrstuvwxyz'
		s = 0
		res = []
		for i in range(len(shifts) - 1, -1, -1):
			s += shifts[i]
			res.insert(0, char[(char.index(S[i]) + s) % 26])
		return ''.join(res)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:

		def shift(char, k):
			idx = ord(char) - ord('a')
			return chr(ord('a') + (idx + k) % 26)
		suffix = 0
		ans = []
		for i in range(len(shifts) - 1, -1, -1):
			suffix += shifts[i]
			ans.append(shift(S[i], suffix))
		return ''.join(ans[::-1])


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		alphabets = 'abcdefghijklmnopqrstuvwxyz'
		n2s = {i: s for (i, s) in enumerate('abcdefghijklmnopqrstuvwxyz')}
		s2n = {s: i for (i, s) in list(n2s.items())}
		S_res = []
		assert len(S) == len(shifts)
		N = len(S)
		roll_over = 0
		for i in range(N):
			s = S[N - i - 1]
			shift = shifts[N - i - 1]
			roll_over = (shift + roll_over) % 26
			S_res.insert(0, n2s[(s2n[s] + roll_over) % 26])
		return ''.join(S_res)


import string

class Solution:

	def shiftingLetters(self, S, shifts):
		start = ord('a')
		res = []
		shifter = lambda char, k: chr((ord(char) - start + k) % 26 + start)
		for i in reversed(range(len(shifts) - 1)):
			shifts[i] += shifts[i + 1]
		for i in range(len(S)):
			res.append(shifter(S[i], shifts[i]))
		return ''.join(res)


class Solution:

	def shiftingLetters(self, S: str, shifts: List[int]) -> str:
		s = sum(shifts)
		n = 0
		a = []
		r = ''
		for i in shifts:
			a.append(s - n)
			n += i
		for i in range(len(a)):
			b = a[i] % (ord('z') - ord('a') + 1)
			c = ord(S[i]) + b
			if c > ord('z'):
				c = ord('a') + c - ord('z') - 1
			r += chr(c)
		return r