Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

880. Decoded String at Index

Time: $O(n)$

Space: $O(1)$

			


class Solution {
 public:
  string decodeAtIndex(string s, int k) {
    long size = 0;  // Length of decoded `s`

    for (const char c : s)
      if (isdigit(c))
        size *= c - '0';
      else
        ++size;

    for (int i = s.length() - 1; i >= 0; --i) {
      k %= size;
      if (k == 0 && isalpha(s[i]))
        return string(1, s[i]);
      if (isdigit(s[i]))
        size /= s[i] - '0';
      else
        --size;
    }

    throw;
  }
};




			


class Solution {
  public String decodeAtIndex(String s, int k) {
    long size = 0; // Length of 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();
  }
}




			


class Solution:
  def decodeAtIndex(self, s: str, k: int) -> str:
    size = 0

    for c in s:
      if c.isdigit():
        size *= int(c)
      else:
        size += 1

    for c in reversed(s):
      k %= size
      if k == 0 and c.isalpha():
        return c
      if c.isdigit():
        size //= int(c)
      else:
        size -= 1