algoadvance

Leetcode 880. Decoded String at Index

Problem Statement

Leetcode Problem 880: Decoded String at Index

An encoded string S is given. To find and write the decoded 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 (say d), the entire current tape is repeatedly written d-1 more times in total.

Given an encoded string S and an index K, find and return the K-th letter (1-indexed) in the decoded string.

Clarifying Questions

1. What is the maximum possible length of string S?
   • This information would help in understanding constraints and edge cases.
2. Can K be larger than the possible length of the decoded string?
   • If K is always valid, it simplifies the problem as we don’t need to handle out-of-bounds cases.
3. What kind of characters does S contain?
   • Let’s confirm if S contains only lowercase letters and digits.

Assuming typical constraints:

• The length of an encoded string S can be up to 100 characters.
• K is always valid and within the bounds of the decoded string length.
• S contains only lowercase letters and digits.

Strategy

1. Simulate Decoding Process:
   • Iterate through the encoded string while tracking the length of the decoded string without actually constructing it.
2. Work Backwards to Find K-th Character:
   • Using the accumulated length, track back through the encoded string to determine the K-th character.
3. Efficiency:
   • Ensure that the solution works efficiently given the possibly large size of the decoded string.

Approach

1. Calculate Length: Traverse through the string to determine the length of the final decoded string.
2. Reverse Approach: Once the size is determined, work backwards from the end of S to find the position of the K-th character.

Code

#include <string>
using namespace std;

class Solution {
public:
    string decodeAtIndex(string S, int K) {
        long long size = 0;  // Long long to handle large sizes
        
        // Step 1: Calculate the size of the final decoded string.
        for (char c : S) {
            if (isdigit(c)) {
                size *= (c - '0');
            } else {
                size++;
            }
        }
        
        // Step 2: Work backwards to find the K-th character.
        for (int i = S.size() - 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--;
            }
        }
        
        return "";  // Should not be reached
    }
};

Time Complexity

Time Complexity: O(N)

• Iterating through the encoded string twice: once to calculate length and once to backtrack.

Space Complexity: O(1)

• Using constant extra space for calculations.

This approach efficiently determines the K-th character in the decoded string without explicitly constructing the entire decoded string, making it suitable for large values of K and large decoded strings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?