880. Decoded String at Index LeetCode Solution

In this guide, you will get 880. Decoded String at Index LeetCode Solution with the best time and space complexity. The solution to Decoded String at Index problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Decoded String at Index solution in C++
4. Decoded String at Index solution in Java
5. Decoded String at Index solution in Python
6. Additional Resources

Problem Statement of Decoded String at Index

You are given an encoded string s. To decode the string to a tape, the encoded string is read one character at a time and the following steps are taken:

If the character read is a letter, that letter is written onto the tape.
If the character read is a digit d, the entire current tape is repeatedly written d – 1 more times in total.

Given an integer k, return the kth letter (1-indexed) in the decoded string.

Example 1:

Input: s = “leet2code3”, k = 10
Output: “o”
Explanation: The decoded string is “leetleetcodeleetleetcodeleetleetcode”.
The 10th letter in the string is “o”.

Example 2:

Input: s = “ha22”, k = 5
Output: “h”
Explanation: The decoded string is “hahahaha”.
The 5th letter is “h”.

Example 3:

Input: s = “a2345678999999999999999”, k = 1
Output: “a”
Explanation: The decoded string is “a” repeated 8301530446056247680 times.
The 1st letter is “a”.

Constraints:

2 <= s.length <= 100
s consists of lowercase English letters and digits 2 through 9.
s starts with a letter.
1 <= k <= 109
It is guaranteed that k is less than or equal to the length of the decoded string.
The decoded string is guaranteed to have less than 263 letters.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

880. Decoded String at Index LeetCode Solution in C++

class Solution {
 public:
  string decodeAtIndex(string s, int k) {
    long size = 0;  // the length of the 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;
  }
};
/* code provided by PROGIEZ */

880. Decoded String at Index LeetCode Solution in 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();
  }
}
// code provided by PROGIEZ

880. Decoded String at Index LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.