algoadvance

Leetcode 848. Shifting Letters

Problem Statement

You have a string s of lowercase English letters and an integer array shifts of the same length.

Call the shift of a letter, the next letter in the alphabet, (wrapping around so that ‘z’ becomes ‘a’).

• For example, shifting ‘a’ results in ‘b’, and shifting ‘z’ results in ‘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

Example 1:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with “abc”.
Arriving at “rpl” by shifting:

• 1st letter by 3 times to ‘d’.
• 1st 2 letters by 5 times to ‘h’ and ‘h’ (starting from ‘d’) resulting in ‘hhc’.
• 1st 3 letters by 9 times to ‘rpl’ due to cyclic shifts.

Clarifying Questions

1. Input Constraints:
   • Is s always non-empty?
   • What is the maximum length of s and shifts?
   • Are the values in shifts non-negative?
2. Output Constraints:
   • Does the output string need to exactly match case-sensitivity?

Strategy

1. Accumulate Shifts:
   • Traverse the shifts array from end to start, accumulating the effect of shifts.
   • Instead of applying the shifts [3, 5, 9] directly, consider cumulative shifts at each step. This way, the 2nd shift also includes the 3rd shift, and the 1st shift includes both 2nd and 3rd shifts.
2. Apply Shifts to String:
   • Modify the original string s by shifting the characters according to the values in the modified shifts array.
   • Use modulo operation to handle the wrapping around (‘z’ shifting to ‘a’).

Example with Cumulative Shifts

For shifts = [3, 5, 9]:

• Update shifts to reflect cumulative shifts:
  • shifts[2] = 9 (no change)
  • shifts[1] = 5 + shifts[2] = 5 + 9 = 14
  • shifts[0] = 3 + shifts[1] = 3 + 14 = 17

Updated shifts array would be [17, 14, 9].

Code

#include <vector>
#include <string>

std::string shiftingLetters(std::string s, std::vector<int>& shifts) {
    int n = shifts.size();
    
    // Accumulate shifts from the end to start
    for (int i = n - 2; i >= 0; --i) {
        shifts[i] += shifts[i + 1];
        shifts[i] %= 26; // Reduce to keep within bounds (a-z)
    }
    shifts[n - 1] %= 26; // also handle the last element
    
    // Apply shifts to string s
    for (int i = 0; i < n; ++i) {
        s[i] = (s[i] - 'a' + shifts[i]) % 26 + 'a'; 
    }

    return s;
}

Time Complexity

• Accumulation of Shifts: O(n), where n is the length of shifts.
• Applying Shifts to String: O(n).

Thus, the overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?