LeetCode 880. Decoded String at Index (Medium)

LeetCode 880. Decoded String at Index: Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Decoded String at Index” or “LeetCode 880.”

Leet Code 2612 Minimum Reverse Operations (Hard)

Approach: Reverse LeetCode 880. Decoded String at Index

Leet code 880, “Decoded String at Index,” challenges us to decode a given string and find the character at a specific index.

Steps of Approach for LeetCode 880 (Decoded String at Index)

1: Calculate Total Length (Leet Code 880.)

• Iterate through the input string character by character.
• If a digit is encounter, multiply the total length by that digit.
• For non-digits, increment the total length.

2: Reverse Traversal

• Start from the end of the string.
• If a digit is encounter, reduce the total length accordingly and update the target index ‘k’ to ensure it remains within bounds.
• If a non-digit character is reach, check if we’ve found the desired index ‘k’ or if the total length becomes zero. If so, return the character.

3: Return Result

• If no character is found in the traversal, return an empty string.

LeetCode 2233 Maximum Product After K Increments (Medium)

Leetcode 775. Find The Global and Local Inversions (Medium)

Code for Reverse Approach (Decoded String at Index)

C++: Leet Code 880

class Solution {
public:
    string decodeAtIndex(string s, int k) {
        //d is deocoded string 
        long long d=0;
        for(auto x:s){

            //check the if digit occure , we will update length of string 

            if(isdigit(x)){
                d=d*(x-'0');                
            }

            //other wise increment by 1

            else{
                d++;
            }
        }

            //we have total length build by the string and no 
          //reverse travesal

        for(int i=s.size()-1;i>=0;i--){

            //check the it char is digit

            if(isdigit(s[i])){

                //we will reduce the length of decoded string by digit we get 

                d/=(s[i]-'0');

                //also we reduce the k index

                k = k % d;
            }
            else{

                //if we reached at end or found the index k 

                if(k==0 || k==d){
                    return string("")+s[i];
                }
                d--;
            }
            
            
        }
            
            
            
        
        return "";
    }
};

Leetcode 316. Remove Duplicate Letters (Medium)

Java: Leet Code 880

public class Solution {
    public String decodeAtIndex(String s, int k) {
        long  d = 0;
        for (char x : s.toCharArray()) {
            if (Character.isDigit(x)) {
                d = d * (x - '0');
            } else {
                d++;
            }
        }
        
        for (int i = s.length() - 1; i >= 0; i--) {
            if (Character.isDigit(s.charAt(i))) {
                d = d / (s.charAt(i) - '0');
                k %= d;
            } else {
                if (k == 0 || k == d) {
                    return String.valueOf(s.charAt(i));
                }
                d--;
            }
        }
        
        return "";
    }
}

LeetCode 389. Find The Difference (Easy)

Python: Decoded String at Index

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        d = 0
        for x in s:
            if x.isdigit():
                d = d * int(x)
            else:
                d += 1
        
        for i in range(len(s) - 1, -1, -1):
            if s[i].isdigit():
                d = d // int(s[i])
                k = k % d
            else:
                if k == 0 or k == d:
                    return s[i]
                d -= 1
        
        return ""

Leet code 799. Champagne Tower (Medium)

JavaScript: Decoded String at Index

var isNum = function(char) {
    return char >= '0' && char <= '9';
}

var decodeAtIndex = function(S, K) {
    var d = [isNum(S[0]) ? 0 : 1];

    for (var i = 1; i < S.length; i++) {
        var char = S[i];
        if (isNum(char)) {
            d.push(d[i - 1] * parseInt(char));
        } else {
            d.push(d[i - 1] + 1);
        }
    }

    for (var i = S.length - 1; i >= 0; i--) {
        K %= d[i];
        if (K === 0 && !isNum(S[i])) {
            return S[i];
        }
    }
};

Leet Code 1048. Longest String Chain (Medium)

Result Analysis :

Leet code 206 Reverse Linked List (EAZY)

Other approached to solve

1. Brute Force Simulation (Not Recommended): You can simulate the decoding process step by step until you reach the ‘k’ position. However, this approach is not efficient and can be very slow for large ‘k’ values.
2. Optimized Search: You can optimize the search by performing a binary search to find the character at the ‘k’ position. Use a similar length calculation as the mathematical approach to determine which part of the string to explore based on ‘k’.
3. Dynamic Programming: Precompute the length of the decoded string for a given prefix and store it in an array. Then, you can use this precomputed information to find the character at the ‘k’ position.