Scale Engineer

Shifting Letters II

Med
#2167Time: O(M * N), where N is the length of the string `s` and M is the number of shifts. For each of the M shifts, we might iterate up to N characters in the worst case.Space: O(N) to store the character array, as strings are immutable in Java.1 company
Patterns
Prefix Sum
Data structures
ArrayString
Companies
Veritas

Prompt

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0.

Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').

Return the final string after all such shifts to s are applied.

 

Example 1:

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
Output: "ace"
Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac".
Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd".
Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".

Example 2:

Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]
Output: "catz"
Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz".
Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".

 

Constraints:

  • 1 <= s.length, shifts.length <= 5 * 104
  • shifts[i].length == 3
  • 0 <= starti <= endi < s.length
  • 0 <= directioni <= 1
  • s consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It iterates through each shift instruction and applies the specified shift to every character within the given range.

Algorithm

  • Convert the input string s into a character array chars.
  • Iterate through each shift in the shifts array.
  • For each shift = [start, end, direction]:
    • Determine the shift amount: 1 for forward, -1 for backward.
    • Iterate from i = start to i = end.
    • Calculate the new character for chars[i] by applying the shift amount. Handle wrapping around the alphabet (e.g., using the modulo operator: (original_position + shift_amount + 26) % 26).
    • Update chars[i] with the new character.
  • After all shifts are processed, convert the chars array back to a string and return it.

Walkthrough

The core idea is to treat the input string as a mutable sequence of characters, like a character array. We loop through every command in the shifts array. For each command [start, end, direction], we run another loop from the start index to the end index. Inside this inner loop, we modify the character at the current position. If the direction is forward (1), we increment the character, wrapping around from 'z' to 'a'. If the direction is backward (0), we decrement it, wrapping from 'a' to 'z'. This process is repeated for all shifts. Finally, the modified character array is converted back into a string.

Here is a Java implementation of this approach:

class Solution {    public String shiftingLetters(String s, int[][] shifts) {        char[] chars = s.toCharArray();        for (int[] shift : shifts) {            int start = shift[0];            int end = shift[1];            int direction = shift[2];            int amount = (direction == 1) ? 1 : -1;             for (int i = start; i <= end; i++) {                int originalPos = chars[i] - 'a';                int newPos = (originalPos + amount + 26) % 26;                chars[i] = (char) ('a' + newPos);            }        }        return new String(chars);    }}

Complexity

Time

O(M * N), where N is the length of the string `s` and M is the number of shifts. For each of the M shifts, we might iterate up to N characters in the worst case.

Space

O(N) to store the character array, as strings are immutable in Java.

Trade-offs

Pros

  • Very straightforward to understand and implement.

  • It follows the problem description literally.

Cons

  • Highly inefficient. The time complexity is the product of the number of shifts and the length of the string, which is too slow for the given constraints.

  • Will result in a 'Time Limit Exceeded' (TLE) error on larger test cases.

Solutions

class Solution {public  String shiftingLetters(String s, int[][] shifts) {    int n = s.length();    int[] d = new int[n + 1];    for (int[] e : shifts) {      if (e[2] == 0) {        e[2]--;      }      d[e[0]] += e[2];      d[e[1] + 1] -= e[2];    }    for (int i = 1; i <= n; ++i) {      d[i] += d[i - 1];    }    StringBuilder ans = new StringBuilder();    for (int i = 0; i < n; ++i) {      int j = (s.charAt(i) - 'a' + d[i] % 26 + 26) % 26;      ans.append((char)('a' + j));    }    return ans.toString();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem