27- Decoded String at Index

The problem can be found at the following link: Question Link

My Approach

1. Initialize decodedLength to 0: This variable will keep track of the total length of the decoded string as we iterate through it. It's initially set to 0.

2. Iterate through each character in the input string s using a for-each loop:

   • If the character c is a digit (checked using isdigit()), it means we need to repeat the characters seen so far in the decoded string by a factor of c - '0' times (convert the character to an integer). So, update decodedLength by multiplying it by c - '0'.

   • If the character is not a digit, it represents a single character in the decoded string, so increment decodedLength by 1.

3. Reverse Iterate through the string s from the end to the beginning (right to left):

   • For each character curr at index i:

     • If curr is a digit, it means that the previous portion of the decoded string is repeated curr - '0' times. To find the effective length of the decoded string up to this point, divide decodedLength by curr - '0', and update decodedLength accordingly.

     • Update k by taking its modulo with the current decodedLength. This ensures that k stays within the bounds of the current portion of the decoded string.

     • If k becomes 0 after the modulo operation or if decodedLength equals k, it means that k corresponds to the current character curr. In this case, return a string containing only curr.

4. If the loop completes without finding a character to return, return an empty string, indicating that the decoded string is not found within the given input parameters.

Time and Auxiliary Space Complexity

• Time Complexity: O(n)

• Auxiliary Space Complexity: O(1)

Code (C++)

class Solution {
public:
    string decodeAtIndex(string s, int k) {
        long long decodedLength = 0;
        for(auto c : s){
            if(isdigit(c)){
                decodedLength = decodedLength * ( c - '0');
            }else{
                decodedLength++;
            }
        }

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

        return "";
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the rishabhv12/Daily-Leetcode-Solution repository.