LC-2381 Medium LeetCode

2381. Shifting Letters II

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 53% Topics: Array, String, Prefix Sum

Reading material

Arrays & Hashing 12 min Strings 12 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

# line sweep
class Solution(object):
    def shiftingLetters(self, s, shifts):
        """
        :type s: str
        :type shifts: List[List[int]]
        :rtype: str
        """
        events = [0]*(len(s)+1)
        for b, e, d in shifts:
            events[b] += 1 if d else -1
            events[e+1] -= 1 if d else -1
        result = []
        curr = 0
        for i in xrange(len(s)):
            curr += events[i]
            result.append(chr(ord('a')+(ord(s[i])-ord('a')+curr)%26))
        return "".join(result)

Solution from kamyu104/LeetCode-Solutions · MIT