Roll Characters of String

Problem Overview

A roll of r moves each of the first r characters one letter forward, with z wrapping around to a.

Intuition

A roll of r moves each of the first r characters one letter forward, with z wrapping around to a. Doing each roll directly could touch most of the string every time. The key question for one character is only how many rolls reach it. Character i is reached by every roll with r larger than i, so the count is a suffix sum. Mark each roll at its last index, sweep from the right while adding the marks, and that running total is exactly the shift for each character.

Algorithm

1Create a count array of size n. For each roll r above 0, increment index r - 1.
2Copy the string into a character array and set a running total to 0.
3Walk from the last index to the first, adding the count at each index to the running total.
4Replace the character with the letter that is running total steps later, taking the result modulo 26.
5Return a new string from the character array.

Example Walkthrough

Input: s = "bca", roll = [1,2,3]

1. The marks are one each at indices 0, 1, and 2.
2. From the right, index 2 has total 1, so a becomes b.
3. Index 1 has total 2, so c becomes e. Index 0 has total 3, so b becomes e.

Output: "eeb"

Common Pitfalls

• A roll of r covers indices 0 through r - 1, so the mark goes at r - 1.
• A roll of 0 shifts nothing. Skip it so it does not index position -1.
• Wrap with modulo 26 after adding the total, or letters past z become symbols.
• Applying each roll directly takes n times q time, which is too slow for long inputs.

Roll Characters of String.java

Java

// Approach: A roll of r shifts the first r characters forward by one letter,
// so character i is shifted once for every roll with r > i. Count each roll at
// its last index r - 1, then walk from the right keeping a running total:
// that total is how far the current character moves, wrapping after 'z'.
// Complexity: O(n + q) time, O(n) extra space, where q is the roll count.
class Solution {

    public String findRollOut(String s, int[] roll) {
        int n = s.length();
        int[] cnt = new int[n];
        for (int r : roll) {
            if (r > 0) {
                cnt[r - 1]++;
            }
        }
        char[] c = s.toCharArray();
        int run = 0;
        for (int i = n - 1; i >= 0; i--) {
            run += cnt[i];
            c[i] = (char) ('a' + (c[i] - 'a' + run) % 26);
        }
        return new String(c);
    }
}

Was this solution helpful?