Shifting Letters II - Practice Coding Problems

Shifting Letters II - Problem

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [start_i, end_i, direction_i].

For every i, shift the characters in s from the index start_i to the index end_i (inclusive) forward if direction_i = 1, or shift the characters backward if direction_i = 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abc", shifts = [[0,1,1],[1,2,0],[0,2,1]]

› Output: "ace"

💡 Note: First shift [0,1,1]: shift indices 0,1 forward → "bcc". Second shift [1,2,0]: shift indices 1,2 backward → "bab". Third shift [0,2,1]: shift indices 0,1,2 forward → "cbc". Wait, let me recalculate: applying difference array gives net shifts of [+1,+1,+1] → "bcd".

Example 2 — Single Character

$ Input: s = "a", shifts = [[0,0,1]]

› Output: "b"

💡 Note: Single shift forward: 'a' becomes 'b'

Example 3 — Wrap Around

$ Input: s = "z", shifts = [[0,0,1]]

› Output: "a"

💡 Note: Forward shift from 'z' wraps around to 'a'

Constraints

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ shifts.length ≤ 5 × 10⁴
shifts[i].length = 3
0 ≤ start_i ≤ end_i < s.length
direction_i is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

String "abc" with shifts [[0,1,1],[1,2,0],[0,2,1]]

Process

Accumulate net shifts per position using difference array

Output

Apply accumulated shifts to get final string

Key Takeaway

🎯 Key Insight: Use difference array to efficiently accumulate multiple range updates in O(n+m) time instead of O(n×m)

Asked in

G Google 25 a Amazon 18 f Facebook 15

The key insight is using a difference array to efficiently handle multiple range updates. Instead of applying each shift operation individually (O(m×n)), we accumulate all changes in O(m) time and apply them once in O(n) time. Best approach is difference array with prefix sum. Time: O(n+m), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Difference Array (Prefix Sum)	O(n + m)	O(n)	Use difference array to efficiently accumulate all range updates
Brute Force - Apply Each Shift	O(m × n)	O(1)	Apply each shift operation directly to the string characters

Difference Array (Prefix Sum) — Algorithm Steps

Create difference array to track net shifts
For each shift operation, update difference array boundaries
Convert difference array to prefix sum
Apply accumulated shifts to each character

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Difference Array

Mark start/end of each range update

Prefix Sum

Convert to actual shift amounts per position

Apply Shifts

Transform each character by accumulated amount

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s, int shifts[][3], int shiftsSize) {
    int n = strlen(s);
    int* diff = (int*)calloc(n + 1, sizeof(int));
    
    // Build difference array
    for (int i = 0; i < shiftsSize; i++) {
        int start = shifts[i][0], end = shifts[i][1], direction = shifts[i][2];
        int shiftAmount = direction == 1 ? 1 : -1;
        diff[start] += shiftAmount;
        diff[end + 1] -= shiftAmount;
    }
    
    // Convert to prefix sum and build result
    char* result = (char*)malloc((n + 1) * sizeof(char));
    int currentShift = 0;
    
    for (int i = 0; i < n; i++) {
        currentShift += diff[i];
        int charCode = s[i] - 'a';
        int newCharCode = (charCode + currentShift % 26 + 26) % 26;
        result[i] = (char)(newCharCode + 'a');
    }
    result[n] = '\0';
    
    free(diff);
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char shiftsLine[10001];
    fgets(shiftsLine, sizeof(shiftsLine), stdin);
    
    // Simple parsing for 2D array
    int shifts[1000][3];
    int shiftsSize = 0;
    
    char* ptr = shiftsLine + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            shifts[shiftsSize][0] = strtol(ptr, &ptr, 10);
            ptr++;
            shifts[shiftsSize][1] = strtol(ptr, &ptr, 10);
            ptr++;
            shifts[shiftsSize][2] = strtol(ptr, &ptr, 10);
            shiftsSize++;
        }
        ptr++;
    }
    
    char* result = solution(s, shifts, shiftsSize);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

n for string length + m for number of shifts operations

✓ Linear Growth

Space Complexity

O(n)

Difference array of size n to store shift amounts

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Difference Array (Prefix Sum) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler