Roll the String
MediumStrings · Paypal
You are given a lowercase string s and a list ranges, where each element is a pair [left, right] of indexes into s.
Rolling a character moves it one letter forward in the alphabet, wrapping around at the end: a becomes b, b becomes c, ..., and z becomes a.
For every pair [left, right], roll each character of s whose index is between left and right, inclusive. Ranges may overlap or repeat; a character covered by k ranges is rolled k times. The final string does not depend on the order in which ranges are applied.
Return the string after all ranges have been applied.
With up to 10^5 ranges over a string of length 10^5, rolling every covered character one range at a time is too slow; aim for time linear in len(s) + len(ranges).
Example 1
- Input:
- s = "paypal", ranges = [[0, 2], [2, 5], [5, 5]]
- Output:
- "qbaqbn"
- Explanation
- Indexes 0, 1, 3 and 4 are covered by one range and move one letter forward (
p->q,a->b). Index 2 is covered twice, soymoves two letters and wraps around toa. Index 5 is also covered twice, solbecomesn.
Example 2
- Input:
- s = "yzz", ranges = [[0, 2], [1, 2], [2, 2]]
- Output:
- "zbc"
- Explanation
- Index 0 is rolled once (
y->z), index 1 twice (z->a->b) and index 2 three times (z->a->b->c).
Example 3
- Input:
- s = "nope", ranges = [[1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3]]
- Output:
- "nbcr"
- Explanation
- The same range is applied 13 times, so
o,pandeeach move 13 letters forward with wraparound, whilenat index 0 is never touched.
Constraints
1 <= s.length <= 10^5sconsists of lowercase English letters0 <= ranges.length <= 10^50 <= left <= right < s.length