Leetcode 848. Shifting Letters

Problem Explanation:

You have been given a string consisting of lowercase letters and an integer array of the same length as the string. In this problem, we need to perform shifts on the characters of the string using the integer values from the array.

The shifting operation is defined as moving the character along the alphabets by a certain number. For example, if we shift the character 'a' by 1, we get 'b', if we shift 'c' by 2, we get 'e' and so on. If we reach 'z' and still have shifts left, we wrap around to the start of the alphabet. So, 'z' shifted by 1 gives 'a'.

Now, the shifting operations are as follows: For each i in the array, we will shift the first i+1 letters of the string by the value of shifts[i].

At the end of all these shifting operations, we need to return the final string.

Let's take an example:

S = "abc", shifts = [3,5,9]

First, we shift the first letter 'a' by 3, yielding 'dbc'.

Next, we shift the first 2 letters 'd' and 'b' by 5, yielding 'igc'.

Finally, we shift the first 3 letters 'i', 'g', and 'c' by 9, yielding 'rpl'.

Thus, our final string after all shifts is "rpl".

Solution Approach:

This problem can be solved using cumulative sum in reverse order.

First, we iterate from the back of the shifts array, and for each position, we calculate the cumulative sum of the shifts. Since shifts can be very large, we reduce each sum to mod 26.

Then, we iterate over the string and for each character, we add the corresponding shift value to it, modulo 26. This value is added to the ASCII value of 'a' to get the shifted character.

C++ Solution

1
2c++
3class Solution {
4    public:
5        string shiftingLetters(string s, vector<int>& shifts) {
6            // Store the result
7            string result;
8            
9            // Calculate the cumulative sum of shifts from the back
10            for (int i = shifts.size() - 2; i >= 0; --i)
11                shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
12                
13            // Apply the shifts to the string
14            for (int i = 0; i < s.length(); ++i)
15                result += (s[i] - 'a' + shifts[i]) % 26 + 'a';
16            
17            return result;
18        }
19};

Python Solution

1
2python
3class Solution:
4    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
5        # Calculate the cumulative sum of shifts from the back
6        for i in range(len(shifts) - 2, -1, -1):
7            shifts[i] = (shifts[i] + shifts[i + 1]) % 26
8            
9        # Apply the shifts to the string
10        return "".join(chr((ord(c) - ord('a') + shifts[i]) % 26 + ord('a')) for i, c in enumerate(s))

Java Solution

1
2java
3class Solution {
4    public String shiftingLetters(String s, int[] shifts) {
5        for (int i = shifts.length - 2; i >= 0; --i)
6            shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
7            
8        char[] chars = s.toCharArray();
9        for (int i = 0; i < chars.length; ++i)
10            chars[i] = (char)((chars[i] - 'a' + shifts[i]) % 26 + 'a');
11            
12        return new String(chars);
13    }
14}

JavaScript Solution

1
2javascript
3var shiftingLetters = function(s, shifts) {
4    for (let i = shifts.length - 2; i >= 0; --i)
5        shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
6        
7    let res = '';
8    for (let i = 0; i < s.length; ++i)
9        res += String.fromCharCode((s.charCodeAt(i) - 97 + shifts[i]) % 26 + 97);
10        
11    return res;
12};

C# Solution

1
2csharp
3public class Solution {
4    public string ShiftingLetters(string s, int[] shifts) {
5        for (int i = shifts.Length - 2; i >= 0; --i)
6            shifts[i] = (shifts[i] + shifts[i + 1]) % 26;
7
8        var chars = s.ToCharArray();
9        for (int i = 0; i < chars.Length; ++i)
10            chars[i] = (char)((chars[i] - 'a' + shifts[i]) % 26 + 'a');
11        
12        return new string(chars);
13    }
14}

PHP Solution

1
2php
3class Solution {
4
5    /**
6     * @param String $s
7     * @param Integer[] $shifts
8     * @return String
9     */
10    function shiftingLetters($s, $shifts) {
11        for ($i = count($shifts) - 2; $i >= 0; --$i)
12            $shifts[$i] = ($shifts[$i] + $shifts[$i + 1]) % 26;
13        
14        $res = '';
15        for ($i = 0; $i < strlen($s); ++$i)
16            $res .= chr((ord($s[$i]) - 97 + $shifts[$i]) % 26 + 97);
17
18        return $res;
19    }
20}

Kotlin Solution

1
2kotlin
3class Solution {
4    fun shiftingLetters(s: String, shifts: IntArray): String {
5        for (i in shifts.size - 2 downTo 0)
6            shifts[i] = (shifts[i] + shifts[i + 1]) % 26
7
8        var res = ""
9        for (i in s.indices)
10            res += ((s[i] - 'a' + shifts[i]) % 26 + 'a'.toInt()).toChar()
11
12        return res
13    }
14}

Swift Solution

1
2swift
3class Solution {
4    func shiftingLetters(_ s: String, _ shifts: [Int]) -> String {
5        var shifts = shifts
6        for i in stride(from: shifts.count - 2, through: 0, by: -1) {
7            shifts[i] = (shifts[i] + shifts[i + 1]) % 26
8        }
9        
10        var res = ""
11        let ascii_a = Int("a".unicodeScalars.first!.value)
12        for (i, c) in s.enumerated() {
13            let ascii_c = Int(c.unicodeScalars.first!.value)
14            let shift = (ascii_c - ascii_a + shifts[i]) % 26 + ascii_a
15            res.append(String(UnicodeScalar(shift)!))
16        }
17
18        return res
19    }
20}

Summary

Whether it's with a high-level language like Python or a low-level language like C++, the essence of the solution remains consistent among the variety of programming languages: calculating the cumulative sum in reverse order first, then applying the corresponding shifts to the string characters. All solutions demonstrated here achieve the same result, although the way of achieving the same may differ based on the language's syntax and available built-in methods or functions.