Perform String Shifts - Practice Coding Problems

Perform String Shifts - Problem

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction_i, amount_i]:

direction_i can be 0 (for left shift) or 1 (for right shift).
amount_i is the amount by which string s is to be shifted.

A left shift by 1 means remove the first character of s and append it to the end. Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Input & Output

Example 1 — Basic Mixed Shifts

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

› Output: "cab"

💡 Note: Left shift by 1: "abc" → "bca". Right shift by 2: "bca" → "abc" → "cab". Final result is "cab".

Example 2 — Only Right Shifts

$ Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]

› Output: "efgabcd"

💡 Note: Net shift calculation: +1 +1 -2 +3 = +3 right shifts. Final result moves last 3 characters to front.

Example 3 — Shifts Cancel Out

$ Input: s = "hello", shift = [[0,2],[1,2]]

› Output: "hello"

💡 Note: Left shift by 2 and right shift by 2 cancel out. Net shift is 0, so string remains unchanged.

Constraints

1 ≤ s.length ≤ 100
s only contains lower case English letters
1 ≤ shift.length ≤ 100
shift[i].length == 2
0 ≤ direction ≤ 1
0 ≤ amount ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

String s and array of shift operations [direction, amount]

Process

Calculate net shift and perform single rotation

Output

Rotated string after all operations

Key Takeaway

🎯 Key Insight: Multiple shift operations can be combined into a single net rotation using modular arithmetic

Asked in

f Facebook 15 a Amazon 8

The key insight is to calculate the net effect of all shift operations rather than performing them individually. Multiple left and right shifts can be combined using arithmetic, then reduced with modular arithmetic. Best approach is the optimized solution: Time O(m + n), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Calculate Net Shift	O(m + n)	O(1)	Calculate total net shift first, then perform one operation
Brute Force - Simulate Each Shift	O(n × m × k)	O(1)	Perform each shift operation one by one

Optimized - Calculate Net Shift — Algorithm Steps

Calculate net shift by summing all operations
Use modular arithmetic to handle shifts larger than string length
Perform single rotation based on net shift

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Net Shift

Sum all operations: [0,1] + [1,2] = -1 + 2 = +1 right

Apply Modulo

Net shift % length = 1 % 3 = 1

Single Rotation

Rotate right by 1: move last 1 character to front

Code -

solution.c — C

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

char* solution(char* s, int shift[][2], int shiftSize) {
    int n = strlen(s);
    if (n == 0) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    int netShift = 0;
    for (int i = 0; i < shiftSize; i++) {
        int direction = shift[i][0];
        int amount = shift[i][1];
        if (direction == 0) {  // left shift
            netShift -= amount;
        } else {  // right shift
            netShift += amount;
        }
    }
    
    // Normalize shift to be within string length
    netShift = ((netShift % n) + n) % n;
    
    char* result = malloc((n + 1) * sizeof(char));
    
    // Perform the rotation
    if (netShift == 0) {
        strcpy(result, s);
        return result;
    }
    
    // Right shift by netShift positions
    strncpy(result, s + n - netShift, netShift);
    strncpy(result + netShift, s, n - netShift);
    result[n] = '\0';
    
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // remove newline
    
    char shiftStr[10001];
    fgets(shiftStr, sizeof(shiftStr), stdin);
    
    // Simple parsing for [[a,b],[c,d]] format
    int shift[1000][2];
    int shiftSize = 0;
    
    char* ptr = shiftStr + 1;  // skip first [
    while (*ptr && *ptr != ']' || *(ptr+1) != '\0') {
        if (*ptr == '[') {
            ptr++;
            shift[shiftSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            shift[shiftSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
            if (*ptr == ',') ptr++;
            shiftSize++;
        } else {
            ptr++;
        }
    }
    
    char* result = solution(s, shift, shiftSize);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

m operations to calculate net shift, plus n characters for final rotation

✓ Linear Growth

Space Complexity

O(1)

Only storing the net shift value and creating result string

✓ Linear Space

25.0K Views

Medium Frequency

~15 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

Optimized - Calculate Net Shift — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler