DDSA Solutions

880. Decoded String at Index

MediumView on LeetCode
ArrayStringStack

Problem Overview

Work backward from total length.

Intuition

Work backward from total length. When k lands in a repeated block, use modulo. Track lengths without materializing the string.

Algorithm

  1. 1Compute length at each step (capped to avoid overflow).
  2. 2Walk backward: if char is digit d, k = ((k-1) % size_before) + 1. If char is letter and k == current size: return that letter.

Common Pitfalls

  • •String can be astronomically large. Only track lengths. Use modulo to reduce k.
880.java
Java
class Solution {
    public String decodeAtIndex(String s, int k) {
        long size = 0; // the length of the decoded `s`

        for (final char c : s.toCharArray())
            if (Character.isDigit(c))
                size *= c - '0';
            else
                ++size;

        for (int i = s.length() - 1; i >= 0; --i) {
            k %= size;
            if (k == 0 && Character.isAlphabetic(s.charAt(i)))
                return s.substring(i, i + 1);
            if (Character.isDigit(s.charAt(i)))
                size /= s.charAt(i) - '0';
            else
                --size;
        }

        throw new IllegalArgumentException();
    }
}
Was this solution helpful?

Related Problems