Scale Engineer

Decoded String at Index

Med
#0834Time: O(L), where L is the length of the fully decoded string. String concatenation and building can be very slow for large strings.Space: O(L), where L is the length of the fully decoded string. This is the major drawback, as L can be up to 2^63 - 1.2 companies
Data structures
StringStack
Companies
PhonePeNational Instruments

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the decoding process described in the problem. It builds the entire decoded string in memory and then retrieves the character at the k-th position. While this is the most straightforward way to think about the problem, it is not feasible given the constraints. The length of the decoded string can grow exponentially, quickly exceeding memory and time limits.

Algorithm

  • Initialize an empty StringBuilder to act as the tape.
  • Iterate through each character of the input string s.
  • If the character is a letter, append it to the StringBuilder.
  • If the character is a digit d, take the current string in the StringBuilder and append it d-1 more times.
  • After iterating through the entire string s, the StringBuilder will contain the fully decoded string.
  • Return the character at index k-1 from the StringBuilder.

Walkthrough

The idea is to use a mutable string, like Java's StringBuilder, to construct the decoded string. We process the encoded string s character by character. When we encounter a letter, we append it. When we see a digit d, we duplicate the current content of our StringBuilder d-1 times. This process continues until we have processed all of s. Finally, we access the character at the k-1 index (since k is 1-indexed) of the resulting string.

class Solution {    public String decodeAtIndex(String s, int k) {        StringBuilder decodedString = new StringBuilder();        for (char c : s.toCharArray()) {            if (Character.isLetter(c)) {                decodedString.append(c);            } else {                long d = c - '0';                String currentTape = decodedString.toString();                for (int i = 0; i < d - 1; i++) {                    decodedString.append(currentTape);                    // A small optimization could be to check if length > k here,                    // but it doesn't save it from memory/time issues on large inputs.                }            }        }        return String.valueOf(decodedString.charAt(k - 1));    }}

This code will fail on examples like s = "a2345678999999999999999" because the length of the decoded string becomes astronomically large.

Complexity

Time

O(L), where L is the length of the fully decoded string. String concatenation and building can be very slow for large strings.

Space

O(L), where L is the length of the fully decoded string. This is the major drawback, as L can be up to 2^63 - 1.

Trade-offs

Pros

  • Simple to understand and implement.

  • Follows the problem description literally.

Cons

  • Extremely inefficient for the given constraints.

  • Will result in OutOfMemoryError as the decoded string can have up to 2^63 - 1 characters.

  • Will result in TimeLimitExceeded due to the massive number of append operations.

Solutions

class Solution { public String decodeAtIndex ( String s , int k ) { long m = 0 ; for ( int i = 0 ; i < s . length (); ++ i ) { if ( Character . isDigit ( s . charAt ( i ))) { m *= ( s . charAt ( i ) - '0' ); } else { ++ m ; } } for ( int i = s . length () - 1 ;; -- i ) { k %= m ; if ( k == 0 && ! Character . isDigit ( s . charAt ( i ))) { return String . valueOf ( s . charAt ( i )); } if ( Character . isDigit ( s . charAt ( i ))) { m /= ( s . charAt ( i ) - '0' ); } else { -- m ; } } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem