Decoded String at Index

MEDIUM

Description

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 k^th letter (1-indexed) in the decoded string.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a2345678999999999999999", k = 1
Output: "a"
Explanation: The decoded string is "a" repeated 8301530446056247680 times.
The 1^st 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 <= 10⁹
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 2⁶³ letters.

Approaches

Checkout 2 different approaches to solve Decoded String at Index. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Simulation

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.

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 Analysis

Time Complexity: O(L), where L is the length of the fully decoded string. String concatenation and building can be very slow for large strings.Space Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Decoded String at Index. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Decoded String at Index

Data Structures:

StringStack

Companies:

PhonePe |National Instruments |