Shifting Letters - Practice Coding Problems

Shifting Letters - Problem

You are given 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, shift('a') = 'b', shift('t') = 'u', and shift('z') = '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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abc", shifts = [3,5,9]

› Output: "rpl"

💡 Note: Position 0 ('a') gets shifted 3+5+9=17 times: a→r. Position 1 ('b') gets shifted 5+9=14 times: b→p. Position 2 ('c') gets shifted 9 times: c→l.

Example 2 — Single Character

$ Input: s = "z", shifts = [25]

› Output: "y"

💡 Note: The character 'z' is shifted 25 times. Since z+25 wraps around, z→y (25 shifts from z brings us to y).

Example 3 — Wrapping Around

$ Input: s = "aaa", shifts = [1,2,3]

› Output: "gfd"

💡 Note: Position 0: a + (1+2+3)=6 shifts → g. Position 1: a + (2+3)=5 shifts → f. Position 2: a + 3 shifts → d.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters
shifts.length == s.length
0 ≤ shifts[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

String 'abc' and shifts [3,5,9]

Calculate Shifts

Each position gets cumulative shifts from its index onward

Output

Apply total shifts to get final string

Key Takeaway

🎯 Key Insight: Work backwards to efficiently calculate cumulative effects

Asked in

G Google 15 f Facebook 12

The key insight is that each position gets shifted by all operations from its index onward. Instead of applying each shift individually, we work backwards to accumulate total shifts efficiently. Best approach uses prefix sum from right to left with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum - Calculate Total Shifts	O(n)	O(1)	Calculate total shifts for each position, then apply once
Brute Force - Apply Each Shift Individually	O(n²)	O(1)	For each shift operation, apply it to all affected positions

Prefix Sum - Calculate Total Shifts — Algorithm Steps

Work backwards through shifts array
Accumulate total shifts for each position
Apply final shift amount to each character once

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from Right

Position 2 gets shift[2] = 9

Move Left

Position 1 gets shift[1] + shift[2] = 5 + 9 = 14

Final Position

Position 0 gets all shifts = 3 + 5 + 9 = 17

Code -

solution.c — C

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

char* solution(char* s, int* shifts, int shiftsSize) {
    int n = strlen(s);
    char* result = malloc((n + 1) * sizeof(char));
    strcpy(result, s);
    
    // Calculate total shifts for each position
    long long totalShift = 0;
    for (int i = n - 1; i >= 0; i--) {
        totalShift += shifts[i];
        int shiftAmount = totalShift % 26;
        int oldChar = result[i] - 'a';
        int newChar = (oldChar + shiftAmount) % 26;
        result[i] = (char)(newChar + 'a');
    }
    
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char line[10001];
    fgets(line, sizeof(line), stdin);
    
    int shifts[1000];
    int count = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        shifts[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char* result = solution(s, shifts, count);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array to calculate cumulative shifts, then single pass to apply

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track running sum of shifts

✓ Linear Space

89.7K Views

Medium Frequency

~15 min Avg. Time

1.2K 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

Prefix Sum - Calculate Total Shifts — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler